Let’s start with the simplest sort of them all: Bubble Sort.

Bubble sort simply loops through an array. If it finds that one value is larger than the value next to it – that value ‘bubbles’ up and up and up until it finally reaches a smaller value. Then the next value bubbles up and does the exact same thing. On and on and on. Bubble Sort is not an efficient algorithm – each value is usually compared to all other values. Bubbles. So many bubbles.

Let’s take an array of six values. We will start our sort by ‘bubbling’ arr[0]. We are going to put arr[0] in its proper spot by comparing arr[0] to arr[1], then arr[0] to arr[2], then arr[0] to arr[3], etc. etc. until we finally compare arr[0] to a larger value. Only then will the bubbling stop for arr[0].

Next we do the same thing to arr[1]. We compare arr[1] to all other values with a higher [i] index in the array. You can see why this sort wastes a lot of computer time. Perhaps there is an even less efficient algorithm, where the value continues to ‘bubble’ even after a ’larger than’ value has been found.

Bubble Sort in C#

int temp;
for (int i = 0; i <= arr.Length - 2; i++) {
    for (int j = 0; j <= arr.Length - 2; j++) {
        if (arr[i] > arr[i + 1]) {
            temp = arr[i + 1];
            arr[i + 1] = arr[i];
            arr[i] = temp;
        }
    }
}

An array element ‘bubbling up’

Of course, `i <= arr.length - 2; is just one way to write our for loop. We could have just as easily written it as:

for (int j = 0; j < arr.Length - 1; j++ ) {
    for (int i = 0; i < arr.Length - 1; i++) {

Keep in mind that

for (int j = 0; j < arr.Length; j++ ) {
    for (int i = 0; i < arr.Length; i++) {

will cause an indexing error as arr[i + 1] is out of bounds of our array. We can not compare the last element to element + 1.

Bubble sort uses the classic outer and inner for loops (Oh! When you realize every problem can be solved just with inner and outer for loops, then comes the crushing disappointment when you learn about time complexity.

for (int i = 0; i <= arr.Length - 2; i++) {
    for (int j = 0; j <= arr.Length - 2; j++) {
    }
}

It is interesting that both iterators, i and j, start at 0. We do not sort the array with i and j = i + 1. That will not work. We simply need multiple passes of the entire array. Each increment of the outer loop (i in our example), represents another full pass. j = i + 1 would not work as our algorithm would not make a full pass through the array, over and over again, which is what Bubble Sort requires.

The neat thing: bubble sort illustrates the basic ‘swap’ we will use in all sorting algorithms:

temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i]= temp;

We will see this again.

Here is how the swap works. We store the value on the left in a temp variable. Take arr[i + 1] and store it into arr[i]. Now we take arr[i] and store it back into the temp variable.

We can use bubble sort to sort our array in the other drection. This would be more like an ‘anchor’ sort (get it – our value is now like an anchor falling to the darkest, deepest depths of the ocean, the opposite of a bubble bubbling up to the heavens). All we would do, of course, is change greater than to less than. arr[i] > arr[i + 1] becomes arr[i] < arr[i + 1];

Note: changing our for loops to iterate backwards, down instead of up, would of course in no way change the final result of our sort.

for (int i = 0; i < arr.Length - 1; i++)
    for (int j = 0; j < arr.Length - 1; j++)

Becomes…

for (int i = arr.Length - 1; i >= 0; i--) {
   for (int j = arr.Length - 1; j >= 0; j--) {
   }
}

Our data is still ends up with the same sorted result. This changing of direction only effects what data gets sorted when – not the final result.

To change the direction of the bubble sort, just flip around the comparison:

if (arr[i] > arr[i + 1]) {

Becomes…

if (arr[i + 1] < arr[i]) {

Here is a cringe animation of bubble sort in reverse:

We have now recreated LINQ OrderBy and OrderByDescending or T-SQL ORDER BY ASC ORDER BY DESC… sort of…

Learning Bubble Sort is not a super practical skill. But I found, for me, the classical sorts were a good way into, finally, starting to understand data structures and algorithms. Also, it is surprising how often I write code, which is bizzarely adjacent to one of the classical sorts. My fingers know the solution because they have drilled these classic computer science problems. It is like how a musician practices scales and arrpegios.. A Chopin Étude is adjacent to simple scales and arpeggios, but only uses them as a jumping off point.