Quicksort

Quicksort is one of the fastest known algorithms for sorting arrays (in average it requires O (n log n) exchanges to order n elements). The algorithm was developed by Tony Hoare in 1960 during his work at Moscow State University. As it counterpart merge sort, it uses divide and conquer paradigm.

640_sir-tony-hoare

Algorithm

Initially, select pivot element in the unsorted array. There are several ways to pick up pivot element:

  1. The pivot element can be either leftmost or rightmost element in partition. This way of selection pivot element is not effective when array is already sorted as this causes worst case.
  2. The best solution which solves problem described in the previous point is to select median using first, middle and last element.
  3. Random element or middle element (middle index), this solution also solves problem which is described in point one.

Note: The second and the third solutions can be considered as modifications of algorithm, because in the earliest versions of algorithm used only the first solution.

Once pivot element is selected, all elements less or equal to the pivot element go to the left and all elements greater or equal to the pivot go to the right. Now, we have two subarrays, one sub-array has elements greater or equal to the pivot and another sub-array which has elements less or equal pivot. For both subarrays, repeat the same actions which were described before, until the sub-array has two or more  elements.

Step-by-step example

As shown in the diagram below, we have the array with following elements [4, 6, 0, 1, 5, 2, 3]. Using this unsorted array we need to apply Quicksort algorithm:

  1. First of all, we select the pivot element, which is 3. Why 3? Because I use an approach when pivot element is always rightmost element in partition.
  2. Farther, all elements less or equal 3 go to the left partition (result: [3, 2, 0, 1]), other elements go to the right partition (result: [5, 6, 4]).
  3. Now, we take left partition [3, 2, 0, 1] and select pivot element, which is 1.
  4. All elements less or equal 3 go to the left partition (result: [0, 1]) in correct order, other elements go to the right partition (result: [2, 3]) in correct order.
  5. Lets come back to the right partition [5, 6, 4] from step #2 and select 4 as pivot element.
  6. All elements less or equal 4 go to the left partition (result: [4]) in correct order, other elements go to the right partition (result: [5, 6]) in correct order.
  7. The end, array is sorted.

quicksort_example

Implementation

My implementation of quicksort can be found on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/sort/QuickSort.java

There are following modifications:

  1. The implementation above can be improved using insertion sort algorithm for small partitions as quicksort is not effective on small volumes of data (for instance, because of recursion which consumes a lot of memory).
  2. As I mentioned in “Algorithm” section pivot selection strategy can be improved using “median of three” rule.
  3. To avoid extremely big recursions you can switch to another sorting algorithm when number of recursions exceeds certain threshold.
  4. Another modification guarantees that, at most O(log N) space is used. For this, you need to use recursion only for the smallest partition, the second partition must be processed in a loop.
Complexity

quicksort_plot

Worst case: O(n^2).

Average case: O(n log n).

Best case: O(n log n).

Conclusion

The fact that quicksort modifications are used in several STL implementations speaks for itself.

Quiz

Q: Which general method use the quicksort?
Click here to check your answer.

A: Exchange method.

Q: Does quicksort require extra memory?
Click here to check your answer.

A: Initially, it required O(n) memory. But, using modifications this can be improved to O(log n).

Q: What is the worst case of quicksort?
Click here to check your answer.

A: O(n^2).

Q: Does quicksort use comparison?
Click here to check your answer.

A: Yes.

Q: Is quicksort stable sorting algorithm?
Click here to check your answer.

A: Initially, no.

Leave a Reply