Understanding Sorting Algorithms

Resources

Big-O Time Complexity from Algorithms

Selection Sort

repeat (numOfElements - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position
copy

The analogy: Imagine a line of people of vary heights. We want to set them from shortest to tallest. We set a marker at the first person. Then from the marker to be the current minimum, and we iterate through the list and compare to the minimum. If the current position is less, we set that position for the current minimum value.

Once we have our minimum and complete the iteration, we compare the marker and the min marker, and if the min marker is less than the marker we swap places.

Selection Sort Implementation

const selectionSort = array => {
  // 1. Set the marker to be the first unsorted member
  // 2. Iterate through the list and set the marker to be an number less than the current marker
  // 3. When list is complete, swap elements
  // 4. Repeat with next marker
  for (let i = 0; i < array.length; i++) {
    let marker = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[marker]) {
        marker = j;
      }
    }

    let tempMember = array[i];
    array[i] = array[marker];
    array[marker] = tempMember;
  }
  return array;
};

module.exports = {
  selectionSort,
};
copy

Bubble Sort

Bubble Sort Implementation

const sort = array => {
  // 1. do (while swapped)
  // 2. set swapped to false
  // 3. set marker to 1
  // 4. iterate through array comparing "sibling" pairs
  // 5. if first sibling less than other, swap siblings
  // 6. set swapped to true
  let swapped = true;
  do {
    swapped = false;
    for (let i = 1; i < array.length; i++) {
      if (array[i] < array[i - 1]) {
        let temp = array[i];
        array[i] = array[i - 1];
        array[i - 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return array;
};

module.exports = {
  sort,
};
copy

Merge Sort Implementation

The best way to picture merge sort is the think that you need to take a queue of people, split them down the middle and continually break those groups into splits of two under each group has a size of max 1. Once this is achieved, we begin to merge these smaller groups back together, sorting as we go.

const mergeSort = array => {
  // 1. base case length === 1 return array
  // 2. set left and right array based on midpoint, recursively call
  // 3. after recursive calls return, merge together
  if (array.length < 2) {
    return array;
  }

  const midpoint = Math.floor(array.length / 2);
  const leftArray = array.slice(0, midpoint);
  const rightArray = array.slice(midpoint);

  mergeSort(leftArray);
  mergeSort(rightArray);

  return merge(leftArray, rightArray, array);
};

const merge = (leftArray, rightArray, array) => {
  let index = 0;

  while (leftArray.length && rightArray.length) {
    if (rightArray[0] < leftArray[0]) {
      array[index++] = rightArray.shift();
    } else {
      array[index++] = leftArray.shift();
    }
  }

  while (leftArray.length) {
    array[index++] = leftArray.shift();
  }

  while (rightArray.length) {
    array[index++] = rightArray.shift();
  }

  return array;
};

module.exports = {
  sort: mergeSort,
};
copy

Quick Sort

Quicksort is a divide + conquer algorithm that sorts a collecton by choosing a pivot point, and partitioning the collection around the pivot, so that elements smaller than the pivot are before it, and elements larger are after it.

It continues to choose a pivot point and break down the collection into single-element lists, before combining them back together to form one sorted list.

Quicksort in action

For this example, we take wisdom from resource [5]:

Also from the article:

Quick Sort in Action

Given the array [9, 12, 9, 2, 17, 1, 6]:

Quicksort in action

Quicksort Recursion

Quicksort conquering

Quicksort here doesn't create a new array and copies elements in correct order, but that is not exactly the case. Quicksort is preferred because it doesn't take up much space during sorting. It does this by swapping instead.

Quick Sort Algorithm

Running the steps part 1

Running the steps part 2

Running the steps part 3

Quick Sort Implementation

The swap function itself is not very complicated. The important thing to remember is the recursive quicksort function and the partitioning.

The mental model and analogy most relevant to myself here is the boxing analogy. A boxer with a dominant right and weaker left will want to bring the left up to the pivot and right down to it.

Consider each partition almost like a sparring session. We set the pivot to be the middle level between the left and right, and then while the left is less than or equal to the right in strength, we iterate through a "training".

Each training requires that while the array[left] is less than the pivot, we push up the left value. While the array[right] is more than the pivot value, we pull it down. Imagine pushing the strength of pushing punches on one side and pulling them back on the other.

Finally, at the end of the that iteration of training, if the left value itself (the index and not the list value) is less than the right, we swap the strength levels (elements) at those places and push the left strength value up again by one and reduce the right by one.

/**
 * Remember by thinking your dominate right should always be strong (bigger) or equal
 * to your left. Within that condition, your left wants to reach the pivot, the right
 * wants to come down to its level. Once all is said and done, if left is smaller than
 * right, swap the values.
 *
 * @param {*} array
 * @param {*} left
 * @param {*} right
 * @returns
 */
const partition = (array, left, right) => {
  const pivot = array[Math.floor((left + right) / 2)];
  while (left <= right) {
    // Continue shifting the left index up until larger than pivot
    while (array[left] < pivot) {
      left++;
    }

    // Continue shifting the right index down until larger than pivot
    while (array[right] > pivot) {
      right--;
    }

    // if left is smaller or equal to right, swap and push left and right indexes down
    if (left <= right) {
      const temp = array[left];
      array[left] = array[right];
      array[right] = temp;

      left++;
      right--;
    }
  }
  return left;
};

/**
 * Remember using "LEFT RIGHT PIVOT, LEFT PIVOT, PIVOT RIGHT" boxing mental model.
 *
 *
 * @param {*} array
 * @param {*} leftIndex
 * @param {*} rightIndex
 * @returns
 */
const quickSort = (array, leftIndex, rightIndex) => {
  // recursion base case
  if (array.length < 2) {
    return array;
  }

  // set pivot through partition
  let pivotIndex = partition(array, leftIndex, rightIndex);

  // recursively call quick sort if pivot - 1 is still larger than left index
  if (leftIndex < pivotIndex - 1) {
    quickSort(array, leftIndex, pivotIndex - 1);
  }

  // recursively call quick sort if right index is still larger than pivot
  if (pivotIndex < rightIndex) {
    quickSort(array, pivotIndex, rightIndex);
  }
  return array;
};

const sort = array => {
  console.log(array);
  quickSort(array, 0, array.length - 1);
  console.log(array);
  return array;
};

module.exports = {
  sort,
};
copy

Quick Sort Shorter Implementation

This pivot uses the first index of the array and also has a bigger space complexity.

// Create an array to sort
var array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 12, 8, 11];

// Basic implementation (pivot is the first element of the array)
function quicksort(array) {
  if (array.length == 0) return [];

  var left = [],
    right = [],
    pivot = array[0];

  for (var i = 1; i < array.length; i++) {
    if (array[i] < pivot) left.push(array[i]);
    else right.push(array[i]);
  }

  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort(array.slice())); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]
copy

Quick Sort Warning

Two unequally-sized partitions can be problematic. Why? See the following:

Problematic Quicksort

Time complexity of quicksort is dependent upon what we choose to be our partition and how sorted the list already is.

Average runtime for an unsorted list + partition close to median is O(n log n).

Average runtime for a sorted (or near-sorted) list or a partition that is far from the median is O(n^2).

Don't use quicksort for nearly sorted lists.

Heap Sort

However, as similar as they are, heap sort is much better than selection sort in one massive way: its performance! Heap sort is basically a super-improved version of selection sort. Yes, it does find the largest element in an unsorted collection and orders it at the back of the list — however, it does all of this work so much faster than selection sort would!

There are two parts to this:

Things to know about heap sort:

Heap Sort Implementation

const sort = array => {
  heapSort(array);
  return array;
};

function heapSort(array) {
  // Build our max heap.
  buildMaxHeap(array);

  // Find last element.
  let lastIndex = array.length - 1;
  const firstIndex = 0;

  console.log('array post build max heap', array);
  // Sorting the heap until we have
  // just one element left in the array.
  // Each iteration "removes" the last index
  // which will be the sorted value.
  while (lastIndex > firstIndex) {
    swap(array, firstIndex, lastIndex);
    heapify(array, firstIndex, lastIndex);
    lastIndex -= 1;
  }

  console.log('array after sorting', array);
}

function buildMaxHeap(array) {
  let midpoint = Math.floor(array.length / 2 - 1);

  // Build a max heap out of
  // all array elements passed in.
  // We are
  while (midpoint >= 0) {
    console.log(array);
    heapify(array, midpoint, array.length);
    midpoint -= 1;
  }
}

function heapify(heap, firstIndex, lastIndex) {
  while (firstIndex < lastIndex) {
    let currentIndex = firstIndex;

    // Finding the indexes of the children from the array
    let leftChild = 2 * firstIndex + 1;
    let rightChild = leftChild + 1;

    // Here we check if one of the two children have a greater value
    // than the value of the heap at the currentIndex. If yes - swap.
    if (leftChild < lastIndex && heap[leftChild] > heap[currentIndex]) {
      currentIndex = leftChild;
    }

    if (rightChild < lastIndex && heap[rightChild] > heap[currentIndex]) {
      currentIndex = rightChild;
    }

    // if the currentIndex hasn't change, return
    if (currentIndex == firstIndex) {
      return;
    }

    // else swap the bigger value for the item at the first index
    swap(heap, firstIndex, currentIndex);
    firstIndex = currentIndex;
  }
}

const swap = (heap, firstItemIndex, lastItemIndex) => {
  const temp = heap[firstItemIndex];
  heap[firstItemIndex] = heap[lastItemIndex];
  heap[lastItemIndex] = temp;
};

module.exports = {
  sort,
};
copy