freeCodeCamp Challenge Guide: Implement Insertion Sort

Implement Insertion Sort


Problem Explanation

  • Insertion Sort assumes that array is divided in two parts:
    1. Sorted (Initially the first element)
    2. Unsorted
  • Each pass, we select an element, and check it against the sorted array.
  • If the selected element is smaller than the last element of the sorted array then we shift the sorted array by 1 until we find the spot to insert the selected element.
  • Insertion sort in action - source
  • Time comlexity of Insertion sort is of O(n2).
  • It’s a stable algorithm.

Solutions

Solution 1 (Click to Show/Hide)
function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let curr = array[i];
    for (var j = i - 1; j >= 0 && array[j] > curr; j--) {
      array[j + 1] = array[j];
    }
    array[j + 1] = curr;
  }
  return array;
}

Relevant Links

4 Likes