DEV Community

Ben Weiser
Ben Weiser

Posted on

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 ]β€ˆ

Top comments (3)

Collapse
 
abiodunjames profile image
Samuel James

valuesToSort is not defined. There is a typo there.

values should be returned and not valuesToSort

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

  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)];
};
Collapse
 
detunized profile image
Dmitry Yakimenko • Edited

Yes, it's a quicksort, in theory. But it won't be quick since it's not in-place. If you're not using the in-place version you're better off with the merge sort most likely. It's stable and it's guaranteed to be O(N*logN). Quicksort is O(N*N) in the worst case. In your version this would happen if you pass in a sorted array.

Collapse
 
benweiser profile image
Ben Weiser

Thanks Dmitry for pointing that out! Next up, in-place sort!