Algorithms: Bubble Sort

Introduction

Bubble sort, also known as sinking sort, is a sorting algorithm that works by looping through an array or list of elements, comparing two elements at a time and swapping them if necessary. It does this until all elements are properly ordered. Let's look at an example of this in action.

Visualization

The algorithm starts at the first card [8] and compares it to the adjacent card [3], since [8] is greater than [3] so they swap positions, this is the core concept of bubble sort.

The algorithm moves through the list checking two elements at a time until each element is in its proper position.

Implementation

Let's break down this algorithm into steps before writing it out in code, so we understand how it works.

• Loop through the array or list.
• As we loop check if the current element is less than or greater than the next element.
• If the current element is greater, then swap the position of the elements, otherwise move to the next element.
• Repeat until no swapping occurs.

The above steps look like this in javascript code

function bubbleSort (array){
    for (var i = 0; i < array.length; i++) { // loop
      if (array[i] && array[i + 1] && array[i] > array[i + 1]) { //comprare
       let currentIndex = array[i];
       array[i] = array[i + 1];   // swap
       array[i + 1] = currentIndex; // swap
     }
  }
  return array
}

There's a problem with the above code, it will only loop through the array once, we need a way to keep the loop going until all elements in the array are sorted and then exit the loop, for this we use a boolean to represent the current state of the array and a while loop to keep the loop going until the state of the array is sorted. In javascript code, the algorithm looks like this.

function bubbleSort (array){
  let unsorted = true;
  while(unsorted){ 
    unsorted = false;
    for (var i = 0; i < array.length; i++) {
      if (array[i] && array[i + 1] && array[i] > array[i + 1]) {
       let currentIndex = array[i];
       array[i] = array[i + 1];
       array[i + 1] = currentIndex;
       unsorted = true;
     }
    }
  }
  return array
}

In the above function, we initialize a variable called unsorted and set the value to true, while unsorted remains true we shall keep looping through the array, when we enter the while loop we assume that we will find the array sorted so we set unsorted to false if the array is not sorted, which we will know when a swap occurs we set unsorted to true and loop through the array again. Only when a swap does not occur and unsorted remains false till the end of the for loop do we end the function because that means the array is sorted.

Time Complexity of Bubble Sort

Bubble sort has a worst and average complexity of O(n²), compared to other sorting algorithms, bubble sort ranks very low in efficiency and it is recommended that programmers do not use it when solving real-world problems.

Conclusion.

Bubble sort is meant to be an educational tool to introduce newbie programmers to the concept of algorithms as it is easy to understand and implement.