Understanding the Bubble Sort Algorithm

A while back, we talked about algorithms like binary search and explained how it works. Today, we’re going to do the same thing with a sorting algorithm called bubble sort. While it’s by far not the most efficient algorithm to use when sorting a list of items, it’s the simplest one to implement and is a great starting point for those interested in learning more about sorting algorithms in general.

First: what is the bubble sort algorithm? Wikipedia defines it as:

…[A] simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list…

Basically, bubble sort works by comparing two adjacent values in a list and, if the value on the left is greater than the value on the right (e.g., 2 comes before 1), it swaps the position of those two values. From there it then checks the next two values (swapping values as needed) until it reaches the last value it sorted (to start, this value is set to the index of the last value in the list).

Once the end of the list has been reached, the index of the last value sorted is decreased by one and the sorting process starts again.

Here’s a visual of how this might look:

The bolded numbers at the end represent the last value that’s been sorted. Once the index of the last value sorted equals 1, the algorithm has finished sorting the array.

 

Write a Bubble Sort Function

The next thing we’ll cover is how you might go about writing a function that uses the bubble sort algorithm to sort an array. Here’s an example of such a function:

function swap(dataArray, index1, index2) {
    var tmp = dataArray[index1];

    dataArray[index1] = dataArray[index2];
    dataArray[index2] = tmp;

    return dataArray;
}

function bubbleSort(data) {
    var pointer = 0,
        maxIndexToCheck = data.length - 1;

    for(; maxIndexToCheck >= 1; maxIndexToCheck--) {
        for(pointer = 0; (pointer + 1) <= maxIndexToCheck; pointer++) {
            if(data[pointer] > data[pointer + 1]) {
                data = swap(data, pointer, (pointer + 1));
            }
        }
    }

    return data;
}

The swap method is just there to swap value arrays, so let’s take a close look at the bubbleSort function. In this function, we first create an outer loop that keeps track of the index of the last value that’s been sorted. By default, this value is equal to the largest index in the array:

...
    var pointer = 0,
        maxIndexToCheck = data.length - 1;

    for(; maxIndexToCheck >= 1; maxIndexToCheck--) {
...

Next, we create a loop that will move through pairs of values in the array comparing the left most value to the value next to it. If the value on the left is greater than the value on the right, we swap those two values’ locations in the array:

...
        for(pointer = 0; (pointer + 1) <= maxIndexToCheck; pointer++) {
            if(data[pointer] > data[pointer + 1]) {
                data = swap(data, pointer, (pointer + 1));
            }
        }
...

Notice how this loop only increments the pointer up to the index of the last value we’ve sorted. As the value of maxIndexToCheck decrements, the number of array values getting checked and swapped drops as well.

Finally, once both loops are complete we return the newly-sorted array.

A Word of Warning

Despite it’s ease of use and implementation, the bubble sort algorithm is hardly the best approach to sorting a large amount of data. The worse-case scenario for this algorithm is O(n<sup>2</sup>) which means that the most iterations needed to sort the algorithm equals the number of items being sorted squared. We’ll get into algorithm speed in a later post, but for now just know that there are better algorithms to use besides this one.

Photo Credit: Evan Leeson