Quicksort is a widely used sorting algorithm known for its efficiency and simplicity. Developed by Tony Hoare in 1960, this sorting technique follows the “divide and conquer” paradigm which makes it a powerful tool for organizing data in ascending or descending order. Programmers find quicksort to be an excellent introduction to sorting algorithms due to its straightforward implementation and elegant design.

The algorithm operates by selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays, where elements less than the pivot are placed on one side, and elements greater than the pivot on the other. This process is then applied recursively to the sub-arrays until the entire array is sorted. Despite its simplicity, quicksort boasts impressive average-case time complexity. As you delve into quicksort, you’ll gain valuable insights into the divide-and-conquer approach widely employed in various problem-solving scenarios.

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)

Table of Contents

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.
  • Block Quicksort – This algorithm performs partition by dividing the 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.

Quicksort Algorithm Complexity

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 Implementation in C by 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 Sort AlgorithmBubble Sort ImplementationInsertion SortSelection Sort