How does Bubble Sort work anyways?

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order – Wikipedia

Sounds easy?

It is! And to be honest there isn't much more to it, so let's look right at the code. It should be very self explanatory. Switch the first and second item if the second one is smaller. Then move on and check if the second element is smaller than the third. If it is switch them again... This is why in the visualzation above the ordered elements start to apear mostly at the left and the right side at first.

    procedure bubbleSort(A : list of sortable items)
        n := length(A)
        repeat
            swapped := false
            for i := 1 to n-1 inclusive do
                /* if this pair is out of order */
                if A[i-1] > A[i] then
                    /* swap them and remember something changed */
                    swap(A[i-1], A[i])
                    swapped := true
                end if
            end for
        until not swapped
    end procedure

Answers

1. Let's look at the pseudocode in more detail. There are two loops in the function. One in line 3 and the for loop in line 5. Both of them iterate roughly over the whole array (or list), so we can say it takes n * n operations. Or if we simplify O(n²) operations. We disregard simple one time operations because in big O notation we only want a rough estimate of the runtime. And loops are usually the structures that add the most impact to the execution duration.

2. I hope it wasn't such a burden for you, but it should have been straight forward. Here are some data sets you can test your algorithm on:

   • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
   • 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
   • 5, 5, 5, 2, 2, 2, 9, 9, 9, 5, 6, 1
   • 6, 4, 8, 3, 8, 4, 9, 5, 0, 4, 2, 6, 8, 0, 6, 4, 3, 3, 5, 7

   The outcomes should be:

   • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
   • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
   • 1, 2, 2, 2, 5, 5, 5, 5, 6, 9, 9, 9
   • 0, 0, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 8, 8, 9

   ---

   Source © Louis Stanko