Skip to content

Latest commit

 

History

History
99 lines (77 loc) · 4.92 KB

quick-sort.asc

File metadata and controls

99 lines (77 loc) · 4.92 KB
Raw

Quicksort

Quicksort is an efficient recursive sorting algorithm that uses divide and conquer paradigm to sort faster. It can be implemented in-place, so it doesn’t require additional memory.

In practice, quicksort outperforms other sorting algorithms like part04-algorithmic-toolbox.asc. And, of course, It also outperforms simple sorting algorithms like part04-algorithmic-toolbox.asc, part04-algorithmic-toolbox.asc and part04-algorithmic-toolbox.asc.

Quicksort picks a "pivot" element randomly and moves all the smaller parts than the pivot to the left and the ones that are bigger to the right. It does this recursively until all the array is sorted.

Quicksort Implementation

Quicksort implementation uses the divide-and-conquer in the following way:

Quicksort Algorithm

  1. Pick a "pivot" element (at random).

  2. Move everything lower than the pivot to the left, and everything more significant than the pivot to the right.

  3. Recursively repeat step #1 and #2 in the sub-arrays on the left and on the right WITHOUT including the pivot.

Let’s convert these words into code!

Quicksort implementation in JavaScript (QuickSort)
link:../../../src/algorithms/sorting/quick-sort.js[role=include]

  1. Partition: picks a pivot and find the index where the pivot will be when the array is sorted.

  2. Do the partition of the sub-array at the left of the pivot.

  3. Do the partition of the sub-array at the right of the pivot.

  4. Only do the partition when there’s something to divide.

The partition function does the real heavy lifting. 🏋️‍♀️

Quicksort implementation in JavaScript (partition)
link:../../../src/algorithms/sorting/quick-sort.js[role=include]

  1. Take the leftmost element as the pivot.

  2. pivotFinalIndex is the placeholder for the final position where the pivot will be placed when the array is sorted.

  3. Check all values other than the pivot to see if any value is smaller than the pivot.

  4. If the current element’s value is less than the pivot, then increment pivotFinalIndex to make room on the left side.

  5. We also swap the smaller element to the left side since it’s smaller than the pivot.

  6. Finally, we move the pivot to its final position. Everything to the left is smaller than the pivot, and everything to the right is bigger.

What would happen if use Quicksort for an array in reverse order?

E.g. [10, 7, 5, 4, 2, 1], if we always choose the first element as the pivot, we would have to swap everything to the left of 10.

So in the first partition, we would have [7, 5, 4, 2, 1, 10]. Then, we take 7 would be the next pivot, and we have to swap everything to the left. Descending arrays are the worst-case for this Quicksort since it will perform O(n2) work. If we do it by the middle (or even better at random) instead of partitioning by the first element, we would have better performance. That’s why we usually shuffle the array before doing Quicksort to avoid edge cases.

link:../../../src/algorithms/sorting/quick-sort.js[role=include]

  1. Convert to array (or clone array). If you want to modify the input, directly remove this line.

  2. Shuffle array to avoid edge cases (desc order arrays)

And you can see the implementation of shuffle below:

Shuffling an array
link:../../../src/algorithms/sorting/sorting-common.js[role=include]

With the optimization, Quicksort has an O(n log n) running time. Similar to the merge sort, we divide the array into halves each time. For more details about how to extract the runtime, go to part01-algorithms-analysis.asc.

Quicksort Properties