Home

Understanding Sorting Algorithms

Resources

  1. Time Complexities of Sorting Algorithms
  2. Big-O For Sorting Algorithms
  3. sorting.at
  4. Visual Go
  5. Pivoting to Quick Sort
  6. Heapify All The Things!

Big-O Time Complexity from Algorithms

AlgorithmBestAverageWorst
Selection SortΩ(n^2)θ(n^2)O(n^2)
Bubble SortΩ(n)θ(n^2)O(n^2)
Insertion SortΩ(n)θ(n^2)O(n^2)
Heap SortΩ(n log(n))θ(n log(n))O(n log(n))
Quick SortΩ(n log(n))θ(n log(n))O(n^2)
Merge SortΩ(n log(n))θ(n log(n))O(n log(n))
Bucket SortΩ(n+k)θ(n+k)O(n^2)
Radix SortΩ(nk)θ(nk)O(nk)

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

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.

  1. Set the first unsorted person as the current minimum.
  2. Go up the entire line and set a new marker on the shortest person.
  3. Once you have the marker and have gone through the line, return to the position of the unsorted person. Swap the unsorted person with the marked shortest person for that iteration.
  4. Repeat from the next unsorted person.

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, };

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, };

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, };

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.

  1. Determine the pivot, which is a somewhat arbitrary element in the collection.
  2. Using that pivot point, partition the larger unsorted colelction into two smaller lists. It uses some smart logic to decide on the partition: it moves all the smaller elements before the pivot element and larger after the pivot element.
Quicksort in action

Quicksort in action

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

We’ll choose the last element as the pivot for now. As it turns out, there are many different ways to choose a pivot element, and what you choose does matter — but more on that in a bit. It’s pretty common to see implementations of quicksort with the last element as the pivot, so that’s what we’ll do here, too.

Also from the article:

A quicksort algorithm should always aim to choose the middle-most element as its pivot. Some algorithms will literally select the center-most item as the pivot, while others will select the first or the last element. But when we say “middle-most” element, what we mean is an element at the median of the entire unsorted collection. This ends up being super crucial because we want the two partitioned halves — the elements smaller than the pivot and the elements larger than the pivot — to be mostly equal. If they’re unequal or lopsided, we can run into some big problems!

Quick Sort in Action

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

Quicksort in action

Quicksort in action

Quicksort Recursion

Quicksort Recursion

Quicksort conquering

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

  1. Choose a pivot (normally highest index)
  2. Choose left reference (lowest index)
  3. Choose right reference (highest but not pivot)
  4. While left ref is less than pivot, move pointer up one to the right. While right ref is more than pivot, move pointer one element to the left.
  5. If both left is greater and right is smaller than pivot, swap the two references.
  6. Once the index of the left is greater than (or equal to) the index of the right reference, swap the pivot with the element at the left reference.
Running the steps part 1

Running the steps part 1

Running the steps part 2

Running the steps part 2

Running the steps part 3

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, };

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 ]

Quick Sort Warning

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

Problematic Quicksort

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:

  1. Build Max Heap - this is done by "Heapify-ing" the array to create a max heap
  2. Sorting - this is done by slowly swapping and "heapify-ing" the array, then reducing the last index to keep the order while iterating.

Things to know about heap sort:

  1. Heap sort transforms the array that pass to it as it sorts; unlike some sorting algorithms, it doesn’t create an entirely separate copy of the input data (it is in-place).
  2. Heap sort also doesn’t need external memory, and is an internal sorting algorithm.
  3. It runs iteratively (and is thus non-recursive)
  4. Compares two elements at a time when it swaps and calls the heapify function, making it a comparison sort algorithm.

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, };