The Bubble Sort

The Bubble Sort is one of the simplest sorts you can write, from a developer’s perspective. Unfortunately, it is one of the slowest to run from the computer’s perspective.

A bubble sort works on the following idea. Given a list of values, start at the top value and look at the next value. If the second value is more than the first value, swap the two values. Then look at the first and third values, swapping them if needed. 

You go through the whole list until you get to the next to last element, replacing the values when needed with each check, so that the smallest (or largest if you are doing a descending sort) value is the topmost element. 

Once that step is completed, you will then move to the second item in the list, and repeat the process so it is the smallest (or largest) of the remaining items. This continues until you check the last two values in your list.

A small array of 10 items sorts fairly quickly. A list of 1,000 items takes a longer time, and I hope you’d never try 10,000,000 items with a bubble sort. The bubble sort is known as an O(n^2) operation.

The Big O notation tells us how many times an operation may occur. With the bubble sort being n squared, it means that the number of operations to sort the list, will be the number of items in the list, squared. \With a bubble sort this is because each item is checked against every item in the list below that item.

So a 10 element array would take 100 operations. A 1,000 element array would take 1,000,000 operations. Jumping from 1,000 to 10,000 elements means a jump to 100,000,000 operations. Even if the operations are fairly fast, there is a huge amount of work to be done.

As the size of the arrays grow, so does the number of checks and potential swaps. Even if you don’t swap the values, all of those elements have to be checked. Numbers are a fairly fast check, but if you are checking two strings it takes longer.

Consider the JavaScript function below for a bubble sort.

// assume an array of integers.
function bubbleSort( arr ) {
    for( var i = 0; i < arr.length - 1; i++) {
        for( var j = i + 1; j < arr.length; j++) {
            if(arr[i] > arr[j]) {
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

Notice that we used a temporary variable to store a value while we are swapping the two values. This is needed to make sure we don’t lose the data when we swap the values.

Some programming languages, like Python, allow us to easily swap the two values with a special assignment operator which can take two values and return two values, such as the code below.

arr[j], arr[i] = arr[i], arr[j];

However, this is fairly rare among language constructs and internally the same process may occur, so who knows if it’s actually any faster in execution.

The Bubble Sort was originally found on Access 2 Learn