DEV Community

Quicksort: A JS Breakdown

Ben Weiser on March 31, 2019

Quicksort is a recursive sorting algorithm that uses the divide and conquer approach. By starting with the simplest base case to check against we c...
Read full post
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!