Quicksort: A JS Breakdown

Quicksort is a recursive sorting algorithm that uses the divide and conquer approach. By starting with the simplest base case to check against we continue to break out list into smaller problems. On average quicksort performs at O(n log n).

Here's the full algorithm,

const quickSort = values => {
  if (values.length <= 1) {
    return valuesToSort;
  }

  let lessThanPivot = [];
  let greaterThanPivot = [];
  const pivot = values.shift();

  for (let i = 0; i < values.length; i++) {
    const value = values[i];
    value <= pivot ? lessThanPivot.push(value) : greaterThanPivot.push(value);
  }

  return [...quickSort(lessThanPivot), pivot, ...quickSort(greaterThanPivot)];
};

Let's break it down,

  if (values.length <= 1) {
    return values;
  }

This is our base case. When using recursion you must always have an exit condition so that your function does not run infinitely causing you to run out of memory. valuesToSort is simply going to be a JavaScript array of integers. If the length of this array is less than equal to or less than one there's nothing more to sort so we exit the function by returning the values. When this function runs our quicksort is complete.

  let lessThanPivot = [];
  let greaterThanPivot = [];
  const pivot = values.shift();

Here we are creating two arrays to hold our values that are smaller than or greater than the pivot value. A pivot can be selected from any index within the array. In our case we are using the shift() method to select the first item in the array.

  for (let i = 0; i < values.length; i++) {
    const value = values[i];
    value <= pivot ? lessThanPivot.push(value) : greaterThanPivot.push(value);
  }

We iterate over the length of the array and check if the value of less than or equal to the pivot. If it is than we push it to the less than array (yes even if it's equal). If this condition is false, then we're going to push it to the greater than array since reason tells us it must be greater.

return [...quickSort(lessThanPivot), pivot, ...quickSort(greaterThanPivot)];

This is where our recursion happens. For the array less than the pivot we're going to call quicksort on this again until there are no more items to be sorted. The same is true for the items that are greater than the pivot. Through each recursive call we return a new array with the items in the correct order.

Try it out with a random array of numbers,

quickSort([50,34,21,2,3,5,7,9])

The result will look like this,

[ 2, 3, 5, 7, 9, 21, 34, 50 ]