The Quadratic Sorting Algorithms: An Overview of Bubble, Selection and Insertion Sort.

Bubble, Selection and Insertion sort are good beginner algorithms to learn as they prime your brain to take on more complex sorting algorithms. These three algorithms are known as the quadratic algorithms because their Big O time complexity is O(n²). In this article, I’ll cover a quick overview of each which will include their general approach, pseudocode and implementation code.

Bubble Sort

Overview

Bubble Sort starts at the beginning of the array and steps through each value, comparing the two values and determining which one is bigger. The bigger number gets swapped to the right. In this manner, the largest values bubble to the top. This is repeated until you reach the last unsorted item (each pass through the array, the total number elements you have to check decreases by 1). A way to optimize is to stop the iteration if no swaps occur.

Pseudocode

1. Create two loops. The top loop should run for as many elements as there are in the array. The nested loop should run until the end of the array the first time, but each time after, should decrease by 1 as the end of the array is already sorted.
2. Starting at the beginning of the array, compare each element to the one next to it. If the value on the left is greater than the value on the right, swap it.
3. Repeat this process until the top loop finishes.
4. Optimization: If a complete pass occurs where no swaps happen, the array is already sorted — return the array.

Implementation Code

function bubbleSort(arr){
  function swap(arr, index1, index2){
    let temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
  }
  let count = 1;
  while (count < arr.length) {
    let swapCount = 0;
    for (let i=0; i<arr.length-count; i++) {
      if (arr[i] > arr[i+1]) {
        swap(arr, i, i+1)
        swapCount++
      }
    }
   if (swapCount === 0) {break}
   count++
 }
   return arr
}

Selection Sort

Overview:

Selection Sort starts at the beginning of the array and loops through every value looking for the smallest value. When it finds the smallest value it saves that values index. At the end of each iteration, you place the smallest value at the index of the top loop.

Pseudocode

1. Create two loops — one nested inside the other. The top loop progresses the array while the nested loop checks that value against all the remaining values.
2. Create a variable called minimum. Compare each element to the minimum. If it is smaller, save that value’s index as the new minimum.
3. After the nested loops iteration is complete, place the value located at the minimum index at the index of the top loop — unless the two values are the same.

Implementation Code

function selectionSort(arr){
  function swap(arr, index1, index2){
    let temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
  }
  for (let i=0;i<arr.length;i++){
    let min = i;
    for (let j=i; j<arr.length;j++){
      if (arr[j] < arr[min]) {
        min = j
      }
    }
    
    if (i !== min) {
      swap(arr,i,min)    
    }
  }
  return arr
}

Insertion Sort

Overview

Insertion Sort begins by looking at the second value in the array, and compares it to the value before it. If the value before it is bigger, you copy the value and place it one spot to the right. You repeat this process until you either reach the beginning of the array or the value in question is not bigger. You then set the index you finished at with the current value you where testing.

Pseudocode

1. Create two loops — one nested inside the other. The top loop starts at the second value in the array. The nested loop starts one value less than the top loop’s index.
2. Create a variable called currentValue which is equal to the value located at the top loop’s index.
3. Starting from top loop’s index, work towards the beginning of the array, comparing the currentValue to each element. If the element is greater than the currentValue variable, copy the element’s value one index greater than its current position.
4. Repeat this process until you reach the beginning of the array or the currentValue is not greater than the valuing you are testing against.
5. Set element’s index to the current Value.

Implementation Code

function insertionSort(arr){
    for (let i=1;i<arr.length;i++){
        let currentVal = arr[i]
        for (var j=i-1;j>=0 && arr[j] > currentVal;j--){
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal
    }
    return arr
}

Big O Complexity

As mentioned above, all these sorting algorithms fall into quadratic — O(n²) — time complexity. The below graph gives a side by side comparison of both time and space complexity.

time and space complexity of bubble, insertion and selection sort

Helpful Tools

Visualizing how an algorithm works helps me greatly. Check out this website: https://visualgo.net/en/sorting which shows a step by step walk through of various sorting algorithms.