Bubble sort is an algorithm that is structurally similar to insertion sort; continuously looping over an array in search of out of place elements. Even then, it is mainly used as an educational algorithm to display alternative ways of sorting arrays as it often does not perform as efficiently as insertion sort.

Assumptions

  • Knowledge of Big-O notation
  • Familiarity with insertion sort is a plus!

What is Bubble Sort?

Bubble Sort, sometimes also called sinking sort, is a basic sorting algorithm that loops over an array, "swapping" pairs of elements that are out of order. The name "bubble" comes from a visual representation of the algorithm where the largest items appear to "bubble up" to the end of the list.

Bubble sort is in place, and also typically stable.

> This algorithm often only performs well on nearly sorted lists, and even then, insertion sort tends to be more efficient, making this algorithm more of an educational item.

/* pseudo-code */
function bubbleSort( int[] arr ) {
    int size = arr.length;
    // Loop over the array
    for( int i = 0; i < size - 1; i++ ) {
        // For each element, loop over and find inversions.
        for( int j = 0; j < size - i - 1; j++ ) {
            // If i and j are inverted..
            if ( arr[j] > arr[j + 1] ) {
                // .. Swap the elements.
                swap( arr, j, j + 1 );
            }
        }
    }
}

// Auxiliary swap function.
function swap( int[] arr, int a, int b ) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

Analyzing Bubble Sort

Worst/Average Best Memory
O(n log n) O(n) O(1)

> Best only occurs in the optimized bubble sort.

Bubble sort, as it is shown above, will loop through the array i times, each time looping through again another j times unconditionally.

As you can see, no matter what, this algorithm will always take time proportionate to O(n<sup>2</sup>) to sort through the array; even when the array is already sorted!

Suppose an array was given where only the first and second elements were out of place and the rest was in order; it wouldn't make much sense for all the other elements to be checked n times to confirm this. To solve that, there exists an optimization that tracks if any inversions were found in its iteration; if no swaps occurred, the algorithm completes. This looks like so:

/* pseudo-code */
function bubbleSortFaster( int[] arr ) {
    int size = arr.length;
    boolean swapped;
    // Loop over the array
    for( int i = 0; i &lt; size - 1; i++ ) {
        // Set the swapped flag to false.
        swapped = false;
        // For each element, loop over and find inversions.
        for( int j = 0; j &lt; size - i - 1; j++ ) {
            // If i and j are inverted..
            if ( arr[j] &gt; arr[j + 1] ) {
                // .. Swap the elements..
                swap( arr, j, j + 1 );
                // .. And set swapped to true.
                swapped = true;
            }
        }
        // Check if any swaps occurred
        if ( not swapped ) {
            // If not, we can exit.
            exit;
        }
    }
}

This optimization allows bubble sort to finish in O(n) time if the array is already sorted. Thanks to this, nearly sorted arrays with nearly sorted elements are able to be sorted very efficiently with bubble sort.

When to use Bubble Sort

As it has been mentioned a few times, bubble sort is really an algorithm only used when teaching it to others for the purpose of education. Even in the cases where it is efficient, such as with a nearly sorted array, algorithms such as insertion sort handle these cases more efficiently on average.

Further Resources