Question

Using Python:

1. A simple sorting algorithm is called a "Bubble Sort" because elements bubble around through the list. It is also called a "Sinking Sort" because the larger values "sink" to the end (bottom) of the list. A bubble sort iterates through a list and swaps adjacent pairs if they are in the wrong order. The sort continues until all elements are correctly ordered.

Example: bubbleSort([0, 1, 8, 4, 3, 2, 9]) - as it begins to process will compare 0 and one and make no change, then 1 and 8 again no change, then 8 and 4 and swap them. This process would repeat until we get [0,1,2,3,4,8,9]

Are there any improvements you can make of the basic implementation?

Write an implementation of a bubble sort

Answer 1

def bubbleSort(lst):
    n = len(lst)
    for i in range(n - 1):
        num_swaps = 0
        for j in range(0, n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                num_swaps += 1
        # Improvement: if no elements were swapped in the previous iteration
        # then the list is already sorted, and we can exit from the function
        if num_swaps == 0:
            break


lst = [0, 1, 8, 4, 3, 2, 9]
print("Original list:", lst)
bubbleSort(lst)
print("Sorted list:", lst)