Quick Sort Algorithm 101

A simple guide to implementing the Quick Sort Algorithm in JavaScript.

Photo by Alessio Lin on Unsplash

The Quick Sort Algorithm (QSA) is yet another path to sorting elements in a list. In our case, we will be implementing the QSA in JavaScript and passing it an array of numbers to be sorted in ascending order.

What is a Quick Sort Algorithm?

The QSA is a kind of divide and conquer algorithm that starts by choosing a pivot point (an arbitrary element in the array), which acts as an anchor to compare all of the other elements.

                // Let's choose 4 as the pivot point  
                             [1,3,4,6,5]

At this point we partition the remaining elements into two sub-arrays based on whether they are less than or greater than the pivot point. There are a number of ways this process can be accomplished which include both in-place sorting or the creation of temporary sub-arrays. The process is repeated for each sub-array (usually through recursion) until all of the elements are sorted.

Here is a general overview of the three most common implementations:

1. The first involves pushing elements from the input array into two separate sub-arrays and concatenating the result once they are both sorted in relation to the pivot point (usually the middle element of the input array). This process is repeated using recursion until everything is sorted.
2. The second (the Hoare Partition Scheme) initiates a scan of the input array from both ends towards the pivot point. If the elements are on the wrong side of the pivot point (greater or less than the pivot) they swap positions in the array. This process continues until the iterators overlap, the pivot point is updated and the process is repeated until the array is fully sorted.
3. The third method (the Lomuto Partition Scheme) typically uses the last element in the input array as the pivot and initiates two iterators to scan the array from start to finish. One iterator keeps track of numbers that are equal to or less than the pivot, while the other ensures that elements between itself and the first iterator hold numbers larger than the pivot.

I am sure you are super confused by those descriptions so here are some resources to help you get a better understanding of each method.

Basic Quick Sort Illustration and Simple Implementation — https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-1.php

Some Pseudo-Code describing the Hoare Partition Scheme — https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

The Hoare Partition Explained — https://www.youtube.com/watch?v=ZHVk2blR45Q

The Lomuto Partition Explained — https://www.youtube.com/watch?v=MZaf_9IZCrc

Implementation

So by this point I hope you have a general understanding of what the QSA does and how it kind of works. In this section we are going to break down each implementation into usable JavaScript code.

Basic QSA

This implementation is easy to understand and keeps things simple.

1. Create 2 sub-arrays, one for the elements less than or equal to the pivot and one for the elements greater than the pivot.
2. Remove the first (or last) element from the input array and turn it into the pivot point.
3. Compare each element to the pivot point and push them to their respective sub-array.
4. Run this process recursively until there is only one element returned.
5. Once the input array is reduced to a single element, concatenate the results in order.

Here is an example using a JavaScript array:

[2,1,4,3]
2 is the pivot
sub-arrays are created [1] [4,3]
[1] gets returned recursively
[4,3] are pushed into [3] [4]
[3] and [4] get returned recursively
[1] pivot point [2] [3] [4] are returned   

Here is the code for the Basic QSA:

const quickSort = (origArray) => {
  
  // base case
  if (origArray.length <= 1) {
    return origArray;
  }
  let left = [];
  let right = [];
  let resultArray = [];
  
  // removes 1st value from input array
  let pivot = origArray.shift();   
  let length = origArray.length;
  // pushes values > or < pivot to sub-arrays 
  for (let i = 0; i < length; i++) {
    if (origArray[i] <= pivot) {
      left.push(origArray[i]);
    } else {
      right.push(origArray[i]);
    }
  };
  // recursive call and results concatenation
  return resultArray.concat(quickSort(left), pivot,    quickSort(right));
};

Hoare Partition QSA

The Hoare Partition implementation is slightly more complex than the previous quick sort function and most people break it into three separate functions for the sake of modularity and readability.

1. Create a swap function that swaps the values of 2 different indexes

// A simple swap function that utilizes a temp variable
const swap = (array, leftIndex, rightIndex) => {
  let temp = array[leftIndex];
  array[leftIndex] = array[rightIndex];
  array[rightIndex] = temp;
};

2. Create a partition to scan the array from both ends and decided whether elements should be swapped.

const partition = (array, left, right) => {
  let pivot = Math.floor((left + right) / 2);
  
  // While the left iterator is less than the right iterator 
  // (ie. they don't overlap)
  while (left < right) {
    // As long as a the elements are less than or greater than 
    // pivot, increment/decrement the iterators towards the pivot
    while (array[left] < array[pivot]) {
      left++
    };
    while (array[right] > array[pivot]) {
      right--
    };
  
    if (left <= right) {
      // swap the elements in the array
      // increment & decrement the iterators
      swap(array, left, right);
      left++
      right--
    };
  };
  // return the left iterator which becomes the new pivot point
  return left;
};

3. Create the actual Quick Sort function, which updates the the elements in the array (in-place). The elements swap according to the pivot point created in the partition function. The Quick Sort function makes recursive calls to itself until the left and right iterators overlap the pivot point and the array is sorted.

const quickSort = (array, left, right) => {
  // Create left and right indexes (start and end of the array 
  // to be searched)
  // Create a pivot point using the partition function which swaps
  // numbers on either side of the pivot and returns an updated 
  // pivot point on each recursive call of quickSort()
  left = left || 0;
  right = right || array.length - 1;
  let pivot = partition(array, left, right);
  if (left < pivot - 1) {
    quickSort(array, left, pivot - 1);
  };
  if (right > pivot) {
    quickSort(array, pivot, right)
  };
  return array;
};

Lomuto Partition QSA

The Lomuto Partition is an alternate implementation that uses the last element in the input array as the pivot point. The partition runs from the beginning of the array to the end using two iterators. The first iterator keeps track of all elements less than or equal to the pivot point and the second iterator keeps track of all elements greater than the pivot point. When the second iterator moves to an element that is less than pivot point it swaps that element with the element at the first iterator. This process repeats until the first (or left iterator) overlaps the pivot point. We can use the same swap function as defined above and slight variation of the quickSort function we already created.

1. Create a swap function that swaps the values of 2 different indexes

// The same swap function as above
const swap = (array, leftIndex, rightIndex) => {
  let temp = array[leftIndex];
  array[leftIndex] = array[rightIndex];
  array[rightIndex] = temp;
};

2. Create a partition to scan the with 2 iterators from left to right, using the last element in the array as the pivot point.

const partition = (array, left, right) => {
  
  // The pivot will always be the last element in the array being
  // scanned, the left is the beginning of the part of the array 
  // being scanned
  let pivot = right;
  let i = left;
  
  // i tracks the small elements and j tracks the larger elements
  for (let j = left; j < right; j++) {
    if (array[j] <= array[pivot]) {
      swap(array, i, j);
      i++
    }
  }
  
  // return the updated i iterator (or left bound)
  return i;
};

3. Create the Quick Sort function, which updates the the elements in the array (in-place). The elements swap according to the pivot point created in the partition function. The Quick Sort function makes recursive calls to itself until the left and right iterators overlap the pivot point and the array is sorted.

const quickSort = (array, left, right) => {
  // Create left and right indexes (start and end of the array 
  // to be searched)
  // Create a pivot point using the partition function which swaps
  // numbers on either side of the pivot and returns an updated 
  // pivot point on each recursive call of quickSort()
  left = left || 0;
  right = right || array.length - 1;
  let pivot = partition(array, left, right);
  if (left < pivot - 1) {
    quickSort(array, left, pivot - 1);
  };
  // We subtract 1 from the pivot to get the updated left index
  if (right > pivot) {
    quickSort(array, pivot - 1, right)
  };
return array;
};

Conclusion

The Quick Sort Algorithm and its various implementations are not the simplest concepts to wrap your head around, but learning how they work and how to build them is a great exercise for any Junior Developer.

The best case time-complexity for a Quick Sort Algorithm is O(n log n), which occurs when both partitions are roughly equal size and run through a Hoare Partition. This happens when the pivot is the median of the array. Unfortunately, given an array of random numbers this is not always the case. The worst case scenario is O(n²).

For more details on time, space complexity and the actual mechanics of a Quick Sort Algorithm check this awesome article by Rohan Paul:

Quick-Sort Algorithm in JavaScript

I highly recommend his work, it was a critical resource that helped me wrap my head around the implementations of both partition functions.

Thanks for reading and keep coding!