Another Post on Bubble Sort

Let's talk about bubble sort, again. Well, okay, for some of you it's again, but I'm new around these parts. Why am I talking about an algorithm that's used very little outside of the classroom? Because spending time with it, regardless of efficiency has helped me chip away at the barriers between logical thinking and my brain.

What is Bubble sort?

Bubble sort is a sorting algorithm. It loops through an array and the largest values will "bubble" to the end until its completely sorted. If you dislike this term, you are not alone. I am a visual person and placing elements towards the end of an array doesn't give the appearance of bubbling up. Unfortunately, the "Placing elements towards the end of the array as they get sorted sort" isn't as catchy.

Let's jump into it. Here is the basic premise of Bubble sort:

• Our input is an unsorted array.
• We loop through the array comparing the first element to the second.
• If it is larger than the second element we swap them.
• Repeat until the array is sorted.
• That's it.

The keystone of this algorithm is the swap. You can write this as a function, or just throw that puppy in there.

Here are two different ways to write a swap function:

//The OG: 

function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

//The ES6 version:

const swap = (arr, i, j) => {
[arr[i], arr[j]] = [arr[j], arr[i]]
}

The first one, in my opinion, is more readable so I will stick to using that. However, I will include a solution at the bottom that includes the second.

In the first swap function, you can see that we set a temporary variable let temp = arr[i]; This allows us to store the element at arr[i] so we do not lose its value. Then we set arr[i] to equal arr[j] and finally set arr[j] to temp. It's pretty straight forward, but the first time I tried to solve this it took me a second to think of adding a third variable. It's important to mention that people with experience would add a third variable without much thought, but if you are coming from a place that doesn't include much logical thinking(ahem, me) something small like this can be difficult.

The next step in creating this algorithm is to add a nested for loop. Usually we want to avoid this kind of thing, but with Bubble sort, we need it. I am going to start with the version of Bubble sort that is not optimized. Trust me, it's better to start this way and then step through the logic of optimization.

Here is the code:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }

  return arr;
}

bubbleSort([4,7,2,1,7,5,9])

 => [1, 2, 4, 5, 7, 7, 9]

Please note that I did not use a swap function, as mentioned above, I just threw that puppy in there.

The first loop will start from the first element in the array and continue towards the end. The inner loop does the same. Within the inner loop is a conditional that checks if the targeted element is greater than the one to the right if (arr[j] > arr[j + 1]), If it is greater then they swap! This happens until the array is completely sorted. Woohoo!

Unfortunately, this method is even more inefficient than bubble sort already is. Add a console.log right after the second for loop and you would see two things, the first being that we are comparing elements that have already been sorted, and second, being we are comparing the last element to an undefined element.

Example showing elements being compared:

4 7
7 2
7 1
7 7
7 5
7 9
9 undefined
4 2
4 1
4 7
7 5
7 7
7 9
9 undefined

To address this problem we set the first for loop to count down the array. Then we set the second for loop to run until the last element that was added to the sorted part of the array. Remember that we are placing elements(bubbling them) towards the end of the array.

It looks like this:

function bubbleSort(arr) {

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

    return arr;
}

bubbleSort([4,7,2,1,7,5,9])

 => [1, 2, 4, 5, 7, 7, 9]

This makes sure that the inner loop doesn't include any of the elements that have been sorted.

Almost there. We can optimize Bubble sort even further. There is still one issue that we haven't talked about. If the array is nearly sorted at the beginning of the function(like this: [1,2,3,4,6,5]) our for loops will not stop looping until their conditions are met. So we have to add some logic in to stop the process when the arr is completely sorted.

Here you go:

function bubbleSort(arr) {
  let didNotSwap;
  for (let i = arr.length - 1; i > 0; i--) {
   didNotSwap = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
        didNotSwap = false;
      }
    }
    if (didNotSwap) break;
  }

  return arr;
}

bubbleSort([4, 7, 2, 1, 7, 5, 9]);

If you can tell we introduced a variable let didNotSwap;. In the first loop, we set this to true. Then after the if statement in the second loop we set it to false. The last piece we added was if (didNotSwap) break;. If there was not a swap then we break out of the loop and return the newly sorted array.

All done! While Bubble sort is not a very efficient algorithm, It does help add to the foundation of logical thinking.

Thank you so much for reading this!

Also here is the extra solution as promised:

function bubbleSort(arr) {
  let didNotSwap;
  for (let i = arr.length - 1; i > 0; i--) {
    didNotSwap = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        didNotSwap = false;
      }
    }
    if (didNotSwap) break;
  }

  return arr;
}

bubbleSort([4, 7, 2, 1, 7, 5, 9]);

Comments

[pentacular]

Bubble Sort is an interesting case, with some useful properties.

It can be applied incrementally, using atomic operations, and be aborted at any point, leaving the data not less ordered.

Which means it's useful for things that benefit from, but do not require, ordering, and where the time available for sorting is uncontrollabe.

Like when operating within a vertical trace interrupt, when those were a thing.

This makes it an interesting contrast to quicksort & bubble sort, radix sort, and the insertion sort families.

It's well worth studying.

[Henry Cook]

Very interesting, thank you!

[Barnett Lobel]

Incredibly helpful explanation. As a beginner to algos, this article definitely cemented my understanding of Bubble Sort and, by extension, lays an excellent foundation for understanding other sorting algos.