How do i calculate the number of comparisons in a bubblesort worstcase scenario

Question

I am new to math and algortithms and very confused. I am looking for the amount of times the numbers get compared in n. in my head it goes like this. if n = 3 in the worst case scenario: [3,2,1] 3 gets compared to 2 and swapped -> [2,3,1] 2 gets compared to 3, 3 gets compared to 1 and swaps -> [2,1,3] 2 gets compared to 1 and swapped [1,2,3] 1 gets compared to 2, 2 gets compared to 3. Done. I get 6 comparisons in this instance.

but in a bubble sort in the worst case there should be as many comparisons as swaps. Can someone explain this to me.

def my_sort(lst):
    lst_sorted = lst.copy()
    n = len(lst_sorted)
    
    change = True

    while change:
        change = False

        for j in range(n - 1):
            if lst_sorted[j] > lst_sorted[j + 1]:
                lst_sorted[j], lst_sorted[j + 1] = lst_sorted[j + 1], lst_sorted[j]
                change = True

    return lst_sorted

i have looked at n*(n-1)/2 which makes it 3 but i have also seen n*(n+1)/2 or even O(n^2).

thank you in advance.

Answer 1

Your understanding is correct.

The worst-case scenario for a bubble sort algorithm involves determining the maximum number of comparisons needed to sort an array of elements (i.e., arrange them in ascending order).

To achieve this, the algorithm starts with comparing and swapping adjacent elements, moving the largest unsorted element to its correct position in each pass. In your example, the largest element is 3. The algorithm iteratively moves it along the array one step at a time until it reaches its correct position at the end of the array.

This process is repeated for the next largest element, which in your case is 2. The algorithm swaps it with adjacent elements until it reaches a position where the element to its right is larger. This continues for each element in the array until the entire array is sorted in ascending order.

So, in summary, the algorithm doesn't just start with the largest element once; it performs multiple passes through the array, ensuring that the largest unsorted element is moved to its correct position in each pass.

Answer 2

Let’s label the key statements in your code:

    while change:                                        // Loop A
        change = False

        for j in range(n - 1):                           // Loop B
            if lst_sorted[j] > lst_sorted[j + 1]:        // Conditional C
                lst_sorted[j], lst_sorted[j + 1] = lst_sorted[j + 1], lst_sorted[j]
                change = True

    return lst_sorted

The comparison of interest happens in Conditional C.

Conditional C is executed on every pass through Loop B. Loop B always executes its body exactly n - 1 times.

Loop B is executed on every pass through Loop A. But it’s not obvious how many times Loop A executes its body.

I previously posted an analysis of bubble sort in this answer. There, I explained that the worst case for Loop A happens when the smallest element is in the largest position, in which case Loop A executes its body n - 1 times.

So, in the worst case, Loop A executes Loop B n - 1 times, and Loop B executes Conditional C n - 1 times, so Conditional C is executed a total of (n - 1)(n - 1) = (n - 1)^2 = n^2 - 2n + 1 times (which is O(n^2) times).

It’s worth noting that this analysis applies to your specific implementation. A bubble sort implementation can short-circuit Loop B on later passes, reducing the overall number of comparisons, but yours does not.