Bubble Sort

Bubble sort is a comparison-based sorting algorithm that iterates through a list of elements, checking adjacent pairs and swapping them if they are not in the correct order. The process is repeated until the entire list is sorted. In each pass, the element is guaranteed to be placed in the correct position.

def bubble_sort(list):
    size = len(list)
    swapped = False
    
    for i in range(size):
        # Bubble sort algorithm guarantees that 
        # for each pass, at least one item is in the correct position.
        for j in range((size - i) - 1)
            if list[j] > list[j + 1]
                temp = list[j]
                list[j] = list[j + 1]
                list[j + 1] = temp
                swapped = True
    
        # when the swapped flag is False, it means the list is already sorted.
        # break out of the loop, when the list is already sorted.
        if not swapped
            break

Note:

• swapped , allows us to check if the list is sorted, allowing us to achieve best case of $O(n)$.
• (size - i) , in every iteration, an element is guaranteed to be in a correct place. This avoids unnecessary check when the element is already in correct position.

For example, bubble_sort([7, 3, 5, 1, 2])

i = 0
[7, 3, 5, 1, 2]
[3, 7, 5, 1, 2]
[3, 5, 7, 1, 2]
[3, 5, 1, 7, 2]
[3, 5, 1, 2, 7] # 7 is placed in the correct position

i = 1
[3, 5, 1, 2, 7]
[3, 5, 1, 2, 7]
[3, 1, 5, 2, 7]
[3, 1, 2, 5, 7] # 5 is placed in the correct position

i = 2
[3, 1, 2, 5, 7]
[1, 3, 2, 5, 7]
[1, 2, 3, 5, 7] # 3 is placed in the correct position

i = 3
[1, 2, 3, 5, 7] # 2 is placed in the correct position

For example: bubble_sort([7, 3, 5, 1, 2])

i = 0:
    # (size - i) - 1 = (5 - 0) - 1 = 4 comparisons
    j = 0: 7 > 3? Yes
        list = [3, 7, 5, 1, 2]
    j = 1: 7 > 5? Yes
        list = [3, 5, 7, 1, 2]
    j = 2: 7 > 1? Yes
        list = [3, 5, 1, 7, 2]
    j = 3: 7 > 2? Yes
        list = [3, 5, 1, 2, 7]

i = 1:
    # (size - i) - 1 = (5 - 1) - 1 = 3 comparisons
    j = 0: 3 > 5? No
    j = 1: 5 > 1? Yes
        list = [3, 1, 5, 2, 7]
    j = 2: 5 > 2? Yes
        list = [3, 1, 2, 5, 7]

i = 2:
    # (size - i) - 1 = (5 - 2) - 1 = 2 comparisons
    j = 0: 3 > 1? Yes
        list = [1, 3, 2, 5, 7]
    j = 1: 3 > 2? Yes
        list = [1, 2, 3, 5, 7]

i = 3:
    # (size - 1) - 1 = (5 - 3) - 1 = 1 comparison
    j = 0: 1 > 2? No

Best Case

Best case happens when the list is already sorted.

For example, bubble_sort([1, 2, 3, 4, 5)]

Calling the function will only iterate through the first pass, then the flag swapped is set to False causing the loop to break. Resulting in the best case, therefore, a linear time complexity, $O(n)$

Worst Case

Worst case happens when the list is sorted in opposite direction.

For example, bubble_sort([5, 4, 3, 2, 1]

Calling the function will result in the following computations:

i = 0:
    # (size - i) - 1 = (5 - 0) - 1 = 4 comparisons
    j = 0: 5 > 4? Yes
    list = [4, 5, 3, 2, 1]
    j = 1: 5 > 3? Yes
    list = [4, 3, 5, 2, 1]
    j = 2: 5 > 2? Yes
    list = [4, 3, 2, 5, 1]
    j = 3: 5 > 1? Yes
    list = [4, 3, 2, 1, 5]
i = 1:
    # (size - i) - 1 = (5 - 1) - 1 = 3 comparisons
    j = 0: 4 > 3? Yes
    list = [3, 4, 2, 1, 5]
    j = 1: 4 > 2? Yes
    list = [3, 2, 4, 1, 5]
    j = 2: 4 > 1? Yes
    list = [3, 2, 1, 4, 5]
i = 2:
    # (size - i) - 1 = (5 - 2) - 1 = 2 comparisons
    j = 0: 3 > 2? Yes
    list = [2, 3, 1, 4, 5]
    j = 1: 3 > 1? Yes
    list = [2, 1, 3, 4, 5]
i = 3:
    # (size - i) - 1 = (5 - 3) - 1 = 1 comparison
    j = 0: 2 > 1? Yes
    list = [1, 2, 3, 4, 5]

From the above, we know it took 1 + 2 + 3 + 4 = 10 comparisons in total.

Suppose, there are n elements in the list then we know it will take 1 + 2 + 3 + 4 + ... + n comparisons in total.

Knowing summation theorem, we know:

$$ 1 + 2 + 3 + ... + n = \sum_{i=1}^{n}i = \frac{n(n + 1)}{2} $$

Expanding n, we get $\frac{1}{2}(n^2 + n)$, since $n^2$ grows the fastest. We can ignore the constant, and $n$.

Therefore, in the worst case, the function grows similar to quadratic function, $O(n^2)$