Quick Sort

Sorting algorithm

  • Uses divide and conquer strategy.
  • Recursive algorithm.
  • The divide step does most of the work.
  • The merge step does nothing.

Performance

Worst case Best case
Θ($$n^2$$) Θ($$nlogn$$)

In practice Quick Sort outperforms Merge Sort, Insertion Sort and Selection Sort.

Pseudo-code

Divide

Divide by choosing any element (pivot) in the sub-array array[p..r].

Partition

  1. Arrange the elements smaller than pivot to its left.
  2. Then arrange the elements bigger than the pivot to its right.
  3. The elements don’t have to be in order. Just to the correct side of the pivot.

Conquer

Recursively call the divide step until the sub-arrays less than 2 elements long.

Combine

Just concatenate the sub-arrays. Since the elements got sorted on the partitioning, there is no work left to do.

My example

  1. function partition (array, leftArray, rightArray, pivot) {
  2. if (!array.length) {
  3. return {leftArray, rightArray};
  4. }
  5. const newLeftArray = array[0] < pivot ?
  6. [...leftArray, array[0]] :
  7. leftArray.slice(0);
  8. const newRightArray = array[0] < pivot ?
  9. rightArray.slice(0) :
  10. [...rightArray, array[0]];
  11. const newArray = array.slice(1);
  12. return partition(newArray, newLeftArray, newRightArray, pivot);
  13. }
  14. function quickSort (array) {
  15. // When to stop
  16. if (array.length < 2) {
  17. return array;
  18. }
  19. // Divide
  20. const pivot = array[array.length - 1];
  21. const { leftArray, rightArray } = partition(
  22. array.slice(0, array.length - 1), [], [], pivot);
  23. // Conquer
  24. const sortedLeftArray = quickSort(leftArray);
  25. const sortedRightArray = quickSort(rightArray)
  26. const sortedArray = [...sortedLeftArray, pivot, ...sortedRightArray];
  27. return sortedArray;
  28. }