Quicksort is a well-known sorting algorithm developed by C.A.R. Hoare: Quicksort. Quicksort is an efficient algorithm based on Divide and Conquer rule and is still a commonly used algorithm for sorting. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays and recursively sorting them.

Computer Journal, Vol. 5, 1, 10-15 (1962)

What are the steps to perform Quick Sort?

  1. Pick an element, called a pivot, from the array.
  2. Partition operation – reorder the array so that elements with values less than the pivot come left, and elements with values greater than the pivot come to the right of the pivot.
  3. Recursively apply the above two steps to the sub-arrays i.e. elements to the left and right of the pivot.

How to pick pivot element?

Pivot is picked up in four possible different ways.

  1. Pick first element as pivot which was used is earliest versions of Quick Sort.
  2. Pick last element as pivot also called Lomuto partition.
  3. Pick a random element as pivot.
  4. Pick median as pivot i.e. choosing the median of the first, middle and last element of the partition for the pivot. This is also called “median-of-three”.

Quicksort Variants

  • Multi-pivot or multiquicksort quicksort – Partition the input variable number of pivots and subarrays.
  • External quicksort – This is a kind of three-way quicksort in which the middle partition (buffer) represents a sorted subarray of elements.
  • Three-way radix quicksort – This algorithm is a combination of radix sort and quicksort.
  • Quick radix sort – This is again combination of radix sort and quicksort with some minor modifications.
  • BlockQuicksort – This algorithm perofmrs partition by dividing th input into constant sized blocks.
  • Partial and incremental quicksort – Only sorts limited number of smallest or largest elements i.e. top 10 elements. Look at std::partial_sort for details.

On average it makes O (n log n) (big O notation) comparisons to sort n items, but in the worst cases it is as slow as bubble sort i.e O(n2).

Pseudocode of Lomuto partition

Quicksort C implementation using different Pivoting Techniques

Quicksort implementation with highlighted steps

The following implementation works in Visual Studio only as it uses text highlighting technique which is specific to Microsoft Windows only.

 

See also: Shell SortBubble SortInsertion SortSelection Sort