# Quick Sort Algorithm 101

--

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

The ** Quick Sort Algorithm (QSA) **is yet another path to sorting elements in a list. In our case, we will be implementing the

**in JavaScript and passing it an array of numbers to be sorted in ascending order.**

*QSA*## What is a Quick Sort Algorithm?

The ** QSA **is a kind of

**algorithm that starts by choosing a**

*divide and conquer***,**

*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

**or the**

*in-place sorting***. The process is repeated for each sub-array (usually through recursion) until all of the elements are sorted.**

*creation of temporary sub-arrays*Here is a general overview of the three most common implementations:

- 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.
- The second (
) 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.*the Hoare Partition Scheme* - The third method (
) 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.*the Lomuto Partition Scheme*

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.

- Create 2 sub-arrays, one for the elements less than or equal to the pivot and one for the elements greater than the pivot.
- Remove the first (or last) element from the input array and turn it into the pivot point.
- Compare each element to the pivot point and push them to their respective sub-array.
- Run this process recursively until there is only one element returned.
- 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 = [];// removes 1st value from input array

let right = [];

let resultArray = [];

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.

- 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) => {// While the left iterator is less than the right iterator

let pivot = Math.floor((left + right) / 2);

// (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]) {// swap the elements in the array

right--

};

if (left <= right) {

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

- 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 Pau****l:**

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!**