Bubble Sort

The algorithm

Bubble sort is a very simple sorting algorithm. It works by repeatedly looping through the array. As we go, we compare adjacent elements. If we find two that are out of order, we swap them and continue on. If we scan through the whole array and don't find anything out of order, then we're done.

Bubble sort is so called because the large items "bubble up" to the end of the array.

The bubble sort algorithm can be expressed in pseudocode:

while the array is changed:
1. set changed to false
2. for each item in the array:
  1. if this item is bigger than the item to the right:
    1. swap them
    2. set changed to true

Here the algorithm is implemented in Java:


public static void bubbleSort(int[] array) {
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i <= (array.length - 2); i++) {
            if (array[i] > array[i + 1]) {
                int temp = array[i + 1];
                array[i + 1] = array[i];
                array[i] = temp;
                changed = true;
            }
        }
    }
}

Analysis

To find the Big-O complexity of this algorithm, we will look at the two loops. The inner loop runs on the order of n times. The first iteration will actually run n - 2 times. Each subsequent iteration will run one fewer times. On average, it will run $\frac{1}{2} n $ times. Remembering that we ignore constant coefficients, that's $O(n)$ times.

The while loop is a bit more complicated, since we can't tell from looking at it how many iterations it will take. But if we think about it, we will see that, in the worst case scenario, we have the biggest array element in the very first position, like this:


99 4 28 16 78 36

That 99 will only move one space to the right for each pass of the algorithm. So in this case, there will be $n - 1$ iterations of the while loop. In the average case, the first item will have to go somewhere in the middle, which would take $\frac{1}{2} n$ iterations. Either way, this loop runs $O(n)$ times as well.

Because these loops are nested, the overall complexity for the algorithm is $O(n^2)$.

Other simple sorting algorithms like selection sort and insertion sort are also $O(n^2)$