Elementary Sorting Algorithms - Day 4April 06, 2020

Basic sorting algorithms

  • Bubble sort
  • Selection sort
  • Insertion sort

Bubble Sort

A sorting algorithm that moves the largest values to the top one at a time. It works by going through the array, comparing two indexes and moving the largest value to the right till all values are sorted.

A naive solution

A basic solution involves 2 loops that compare the values at 2 indexes and always moves the largest one to the right.

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

  return arr
}

This algorithm involves pushing the largest variable to the right. After the first loop, we can say we’re certain the array item on the last index is sorted. As the algorithm progresses, we can be sure items on the far right are well sorted. But this algorithm still loops through them. Here’s a better solution

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

  return arr
}

With this algo, we don’t sort items on the far right once they’re sorted.

Selection Sort

In selection sort, we still have an inner and outer loop. The goal is to compare the current index with all members of the array, searching for the smallest of all. We store a pointer to the smallest item and move it to the far left when we’re done looping.

Here’s what it’ll look like

let selectionSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    // set smallest value to the value of the index
    let smallestValue = i
    // set j = i + 1, so the sorted elements at the far left are not resorted
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[smallestValue]) {
        // reset smallest value if item compared is smaller
        smallestValue = j
      }
    }

    // swap smallest value with current index
    if (i !== smallestValue) {
      let temp = arr[i]
      arr[i] = arr[smallestValue]
      arr[smallestValue] = temp
    }
  }

  return arr
}

Insertion Sort

Builds up the sort by gradually creating a larger left half which is always sorted

let insertionSort = inputArr => {
  let length = inputArr.length
  for (let i = 1; i < length; i++) {
    let sortKey = inputArr[i]
    let j = i - 1
    while (j >= 0 && inputArr[j] > sortKey) {
      inputArr[j + 1] = inputArr[j]
      j = j - 1
    }
    inputArr[j + 1] = sortKey
  }
  return inputArr
}

Comparison of Big O of Sorting Algorithms

Algorithm Time Complexity Time Complexity Time Complexity Space Complexity
Bubble Sort O(n) O(n2) O(n2) O(1)
Insertion Sort O(n) O(n2) O(n2) O(1)
Selection Sort O(n2) O(n2) O(n2) O(1)