What is the output of this code snippet?
def bubblesort(lst): for passesLeft in range(len(lst)-1, 0, -1): for index in range(passesLeft): if lst[index] > lst[index + 1]: lst[index], lst[index + 1] = lst[index + 1], lst[index] return lst l=[27, 0, 71, 70, 27, 63, 90] print(bubblesort(l))
The bubble sort does exactly what you’d expect it to do. It sorts an input list by treating each element as a bubble that climbs up the list. Each bubble rises as long as it is greater than the list elements. If a list element is smaller or equal to a list element, the bubble stops to rise and the list element starts to bubble up.
The precise algorithm works as follows. The outer index variable
border marks the index after which the right-hand list elements are already sorted.
The inner index variable i goes from left to right until it reaches the index variable border. On its way to the right, it switches two subsequent list elements if the first element is larger than the second element.
Hence, after the first pass, the largest element in the list is on the right. As this right-most element is already sorted, we can reduce the size of the list to be sorted by one, i.e., decrement the variable border.
Next, the second largest element will rise to the top and the procedure repeats.
Study this basic algorithmic pattern carefully. Every computer scientists and every great coder must know it.
Are you a master coder?
Test your skills now!
[0, 27, 27, 63, 70, 71, 90]