Quick Sort Algorithm 101

Photo by Alessio Lin on Unsplash

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]
  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.

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.
[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
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;
};
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;
};
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;
};
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;
};
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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store