Bubble sort / Sinking sort

ProgrammingProgrammingAlgorithmsSorting
test
Photo by Diana Orey on Unsplash

When you have a set of data, you often need to sort it. Before we had computers to help, we were doing this by hand. While humans are very good at making broad visual comparisons, using programming to sort data saves incredible amounts of time. This post looks at one of the most common starter sorting algorithms — bubble sort.


Bubble sort

Let’s start with a basic set of data. We have 10 numbers, they’re out of order, and we’re going to use bubble sort to sort them.

[9, 6, 2, 7, 1, 0, 5, 3, 4, 8]

Quick note: Bubble sort has also been referred to as sinking sort. The idea is that lighter values will ‘bubble’ up to the front of the array, and heavier values will ‘sink’ towards the end of the array as the algorithm is performed.

Bubble sort is not a very performant algorithm. Most algorithms often have to visit each item within n. When you look at a set of data n, like that set of n = 10 above, the amount of operations that happen in each step help decide the time complexities of the algorithm. More on that in another post.

We have this array of numbers 0 through 9, and we learned a little bit about for loops and variables in the Programming basics post. We know we can iterate over a range of data, and we have this unsorted number array.

Let’s use this data to set up a basic javascript file to do this. For now, let’s just print each item in the array so we know we’re stepping through each step, no more, no less.


bubbleSort.js----unfinished

let unsortedNumbers = [9, 6, 2, 7, 1, 0, 5, 3, 4, 8]

function bubbleSort(arrayToSort) {

  for(let i = 0; i <= arrayToSort.length - 1; i++) {
    console.log(arrayToSort[i])
  }

  return arrayToSort
}

bubbleSort(unsortedNumbers)

Quick notes:

  • A for loop was created, the index i starts at 0, and ends at the length of the array that was passed in. Keep in mind, an array’s first value is at index 0.
  • We continue to the next step until we get to the array’s length minus 1 arrayToSort.length - 1. An array’s length is the amount of values in the array. In this case we have 10.

    • Since the index starts at 0 for the array, and we have the length of 10, we can subtract that and count from 0 to 9 (10 numbers). Now we can use this iterator to point to which index we want from the array. We do that in the console.log(<printing value of array's index here>)
    • If we were outside of the bounds of the array, say array[200], that position would be undefined and not one of our available values to sort.
  • We return the unsorted array arrayToSort for now. This is helpful for this function because we can use the returned sorted value in variables.
  • We made a variable unsortedNumbers that is an array of our unsorted numbers from above. We can reference this later, which we do in the bubblesort(arrayToSort) function. arrayToSort is just a reference to the unsorted array you pass into the bubbleSort function.
  • We are using console.log() to print each item in the array for now. You can view this in your browsers developer options. This is often the F12 key for browsers.

We have our for loop iterating over each item, and printing to the console what the value is at that index. The result right now looks like this:

printing value of each item index in array

So we are successfully iterating over each item in the array, and printing what it’s value is. That’s a great first step! Now lets see if we can move these items intelligently, and sort them.

One thing that may not be apparent is we can say “give me the value of the item at this index of the array”, like we do when we print. We can also say “give me the value at this index + 1”, which will show the value next to the current index in the for loop. We can use this, and some comparison operators to determine which value is higher or lower, and compare values as we travel along the array. We can

The way that bubble sort handles comparing the numbers is by setting up 2 for loops. This can really be thought of as:

Compare every number to every other number. Swap higher values on the left with lower values on the right. When we finish comparing the first number to all the rest, we know the last number is the the highest value. We then perform the next comparison run, do the same thing, until you get to the end, which the last item will be the 2nd highest value, and so on.

Here is the algorithm now sorting our data set:


bubbleSort.js

let unsortedNumbers = [9, 6, 2, 7, 1, 0, 5, 3, 4, 8]


console.log('before sorted:')
console.log(unsortedNumbers)


function bubbleSort(arrayToSort) {

  for(let i = 0; i <= arrayToSort.length - 1; i++) {
    
    for(let j = 0; j <= arrayToSort.length - 1; j++) {

      if(arrayToSort[j] > arrayToSort[j + 1]) {

        let temp = arrayToSort[j + 1]
        arrayToSort[j + 1] = arrayToSort[j]
        arrayToSort[j] = temp

      }

    }

  }

  return arrayToSort
}


console.log('after sorted:')
console.log(bubbleSort(unsortedNumbers))

Quick notes:

  • Instead of printing each individual item to the console, we print the entire array. Once before the sort, and once after the sort.
  • We call the bubbleSort function from within the console.log() function.
  • Both for loops i and j: for(let i = 0; i < arrayToSort.length - 1; i++) ... are going through every item in the array.
  • if(arrayToSort[j] > arrayToSort[j + 1]) here we say is the item at array[j] index greater than array[j+1]? In other words, is the item on the left greater than the item on the right?

    • If we had j = 0, and the array looked like this: [5, 4], we would be asking on our first run “Is 5 greater than 4?”
  • In this if statement section we swap the values in the array:

    • We’re setting the right side value, from which we’re comparing, to a temporary variable called temp. We then set that right side value to the left value. Since the right side and left side are the same thing at this point, we set our left side value to our temporary value (right side from before)

      let temp = arrayToSort[j + 1]
      arrayToSort[j + 1] = arrayToSort[j]
      arrayToSort[j] = temp

Here is the console showing the before and after array.

showing data array before and after bubble sorted

We’ve made a great achievement here! Even though it is the first sorting algorithm usually learned, and is not great with massive data sets, we still have a tool in our belt that we can now use to solve future issues. This is very important, and you are encouraged to create a knowledge base of your own for referenced learning. Over time we will learn better algorithms, but applying the knowledge you learn is crucial for understanding the reasons why some of these algorithms may work better than others. (More than likely running into pitfalls and learning by failure, which is ok!)


Afterthoughts

This post was meant to stay simple, but there are also some things we can do to improve our algorithm even further. One quick change we could do is after each iteration from the first for loop, make sure the length does not include the values that are already sorted for our second loop. We would go to the end on the first run, then go to the end - 1 on the second run, - 2 for the third…

Our change would be in our inner for loop condition. Instead of saying:

for(let j = 0; j <= arrayToSort.length - 1; j++)

We would modify our ‘go until’ condition:

j <= arrayToSort.length - 1;

to this:

j <= arrayToSort.length - 1 - i;

We would be taking i elements away from the limit for that run of comparisons.

The first run i would equal 0, so we would do all comparisons to the end. We would move the largest value to the end of the array in that first run.

In the second run, i would equal 1 so we would do all the comparisons to the end minus i, or 1. The minus 1 represents the last position of the array, which we know to be the largest value from the last run.

i would keep increasing until the comparisons left with only the array[0] and array[1] positions.

By adding this change - i to our existing algorithm, we have brought our number of comparisons down from 100 to 55.

While this is an improvement upon our bubblesort algorithm, the fact that we are iterating over each n (first for loop) * n (second for loop) times we can expect that as our array size goes up, we’re going to increase how much time it takes for the operation to complete exponentially. That leaves bubblesort well suited for education, as there are many other more performant algorithms have been developed for sorting.

Thanks for reading!