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, and replace the values so that the smallest (or largest if you are doing a descending list) value is on top. 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 a 1,000 items takes a long time, and I hope you’d never try 10,000 items with a bubble sort. The bubble sort is known as an O(n^2) operation. Meaning that there will be the number of times in the to be sorted list, squared operations.

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.

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 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.

A Special Case for Bubble Sort

We can speed this up a little bit for special cases where many times our data will already be pre-sorted. We’ll use a flag, or a boolean variable we set if a condition is met, when we need to check for something later on. 

In this case, we can set a flag to see if there were any swaps, if not, then we can exit out of the sort because it is already sorted. It’s a fairly simple modification, and might look something like the following in C#:

// assume an array of integers is passed into the bubble sort function
// it will return the sorted array
static int[] bubbleSort(int[] arr )
{
            // bubble sort variables needed
            int temp = 0;
            bool swapped = true;
// notice the flag is used to see if we can break out of the loop
            for(int x = 0; x < arr.Length - 1 && swapped; x++)
            {
	    // reset the flag, to force a break in the loop unless we swap
                swapped = false;
                for(int y = x + 1; y < arr.Length; y++)
                {
                    if(arr[x] > arr[y])
                    {
                        temp = arr[x];
                        arr[x] = arr[y];
                        arr[y] = temp;
                        swapped = true;
                    }
                }
            }

return arr;
}

Notice that this checks each loop through, so it the given data is partially sorted, it will stop once it performs a loop with no more swaps. However, this is fairly rare, so while you can exit from your sort faster, it is rare to do so, and thus a bubble sort isn’t the best way to write a sort algorithm.

In both of these cases, we have used arrays. However, using a linked list is also possible. However, instead of a for loop, you would use a while loop to go through the different elements until you reached the end. 

Doing a swap with a linked list is a little more challenging, but it isn’t impossible. However, if you have gotten to a section where you need a linked list because you have too many elements to use an array, you have probably got far too many elements to use a bubble sort on.

So let’s look at a couple of different types of sorting algorithms you can use to be more efficient.

Bubble Sort was originally found on Access 2 Learn