The Quadratic Sorting Algorithms

February 12, 2021

Bubble Sort, Selection Sort, and Insertion Sort make up a trio of sorting algorithms that are commonly referred to as the Quadratic Sorting Algorithms. This is because, generally speaking, their time complexity is quadratic or O(n²). They each represent ways of sorting data, though their approaches to sorting and swapping data elements are different. These are by no means the only sorting algorithms, and are often not super efficient, but they're good to know and come up often in coding interviews.

Efficiencies and visualizations of these different algorithms (among others) can be observed here.

Bubble Sort

function bubbleSort(arr) {
  const swap = (arr, index1, index2) => {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  };

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

Bubble Sort Explanation

Bubble Sort works by letting the largest numbers of the array "bubble up" to the end of the array by using two loops, one nested within the other. The outer loop starts at the end of the array, and the inner loop starts at the beginning of the array.

The swapping only happens within the inner loop, comparing arr[j] and the next item, arr[j + 1]. If arr[j] is greater than arr[j + 1] then we swap and continue comparing through the loop.

The outer loop works backwards, ensuring that the end of the array is sorted and we don't duplicate effort. After the completion of the first outer loop, we know the last item of the array is the largest item present in the data, so we don't need to do that comparison again. After the second round, we know the last two items of the array are sorted, and so on.

Bubble Sort Breakdown

function bubbleSort(arr) {
  const swap = (arr, index1, index2) => {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  };

  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      console.log("**Comparing**");
      console.log(arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) {
        console.log("**Swapping**");
        swap(arr, j, j + 1);
        console.log(arr[j], arr[j + 1]);
      }
      console.log("**Array**");
      console.log(arr);
      console.log("**********");
    }
  }
  return arr;
}

bubbleSort([4, 5, 2, 1, 3]);

/*
  [4, 5, 2, 1, 3];
   ^  ^ - No Swap.
  [4, 5, 2, 1, 3];
      ^  ^ -Swap!
  [4, 2, 5, 1, 3];
         ^  ^ - Swap!
  [4, 2, 1, 5, 3];
            ^  ^ - Swap!
  [4, 2, 1, 3, 5];
   ^  ^ - Swap!
  [2, 4, 1, 3, 5];
      ^  ^ - Swap!
  [2, 1, 4, 3, 5];
         ^  ^ - Swap!
  [2, 1, 3, 4, 5];
   ^  ^ - Swap!
  [1, 2, 3, 4, 5];
      ^  ^ - No Swap.
  [1, 2, 3, 4, 5];
   ^  ^ - No Swap.
  Return: [1, 2, 3, 4, 5];
*/

Bubble Sort Time and Space Complexity

Complexity	Big O
Time (Best)	`O(n)`
Time (Average)	`O(n²)`
Time (Worst)	`O(n²)`
Space	`O(1)`

Selection Sort

function selectionSort(arr) {
  const swap = (arr, index1, index2) => {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  };

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j;
      }
    }
    if (i !== lowest) {
      swap(arr, i, lowest);
    }
  }
  return arr;
}

Selection Sort Explanation

Where Bubble Sort works to allow the largest numbers to bubble up to the end of the array, Selection Sort works in sort of the opposite way. This algorithm also has two loops, one nested within the other. Each iteration of the outer loop "selects" the lowest value and pushes it to the front of the array.

The outer loop and inner loop both start from the beginning of the array and move to the end. The inner loop compares the first value to the subsequent values. If the subsequent value is lower than the first value, the index of the subsequent value is bookmarked as the lowest, or arr[lowest], and that value is the one that then gets compared to the rest of the array. When the inner loop ends, if the index of the bookmarked lowest value is not the same as the index of of the outer loop, then the item at arr[i] is swapped with arr[lowest].

Selection Sort Breakdown

function selectionSort(arr) {
  const swap = (arr, index1, index2) => {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  };

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      console.log("**Comparing**");
      console.log(arr[lowest], arr[j]);
      if (arr[lowest] > arr[j]) {
        console.log("**Setting new lowest**");
        lowest = j;
        console.log(`**Lowest Index: ${lowest}**`);
      }
    }
    if (i !== lowest) {
      console.log("**Swapping**");
      swap(arr, i, lowest);
      console.log(arr[i], arr[lowest]);
    }
    console.log("**Array**");
    console.log(arr);
    console.log("*************");
  }
  return arr;
}

selectionSort([4, 5, 2, 1, 3]);

/*
  - Set initial lowest index for loop (0).
  [4, 5, 2, 1, 3];
   *  ^ - No new lowest index (0)
  [4, 5, 2, 1, 3];
   *     ^ - New lowest index (2)
  [4, 5, 2, 1, 3];
         *  ^ - New lowest index (3)
  [4, 5, 2, 1, 3];
            *  ^ - No new lowest index (3). Swap!
  - Set initial lowest index for loop (1).
  [1, 5, 2, 4, 3];
      *  ^ - New lowest index (2)
  [1, 5, 2, 4, 3];
         *  ^ - No new lowest index (2)
  [1, 5, 2, 4, 3];
         *     ^ - No new lowest index (2). Swap!
  - Set initial lowest index for loop (2)
  [1, 2, 5, 4, 3];
         *  ^ - New lowest index (3)
  [1, 2, 5, 4, 3];
            *  ^ - New lowest index (4). Swap!
  - Set initial lowest index for loop (3).
  [1, 2, 3, 4, 5];
            *  ^ - No new lowest index (3).
  Return: [1, 2, 3, 4, 5];

*/

Selection Sort Time and Space Complexity

Complexity	Big O
Time (Best)	`O(n)`
Time (Average)	`O(n²)`
Time (Worst)	`O(n²)`
Space	`O(1)`

Insertion Sort

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

Insertion Sort Explanation

Insertion Sort works by sorting the left side of the array, item by item, and "inserting" the next item outside of the sorted portion into its correct place.

The algorithm loop starts at the second item in the array and runs to the end of the array, comparing the current item to its predecessor. If the current item is less than the predecessor, we move it up into the sorted portion of the array, and make space for the items that are greater than it by increasing their index values.

Insertion Sort Breakdown

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    console.log("**Comparing**");
    console.log(arr[i - 1], currentVal);
    let j;
    for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      console.log(`**${arr[j]} is greater than ${currentVal}**`);
      arr[j + 1] = arr[j]
    }
    console.log(`**${arr[j]} is not greater than ${currentVal}**`);
    console.log(`**Placing ${currentVal} after ${arr[j]}**`);
    arr[j + 1] = currentVal;
    console.log("**Array**");
    console.log(arr);
    console.log("*************");
  }
  return arr;
}

insertionSort([4, 5, 2, 1, 3]);

/*

  [4, 5, 2, 1, 3];
   *  ^ - No move.
  [4, 5, 2, 1, 3];
      *  ^ - Move up!
  [4, 2, 5, 1, 3];
   *  ^ - Move up!
  [2, 4, 5, 1, 3];
   ^ - No Move.
  [2, 4, 5, 1, 3];
         *  ^ - Move up!
  [2, 4, 1, 5, 3];
      *  ^ - Move up!
  [2, 1, 4, 5, 3];
   *  ^ - Move up!
  [1, 2, 4, 5, 3];
   ^ - No move.
  [1, 2, 4, 5, 3];
            *  ^ - Move up!
  [1, 2, 4, 3, 5];
         *  ^ - Move up!
  [1, 2, 3, 4, 5];
      *  ^ - No move.
  Return [1, 2, 3, 4, 5];

*/

Insertion Sort Time and Space Complexity

Complexity	Big O
Time (Best)	`O(n²)`
Time (Average)	`O(n²)`
Time (Worst)	`O(n²)`
Space	`O(1)`