Quicksort Algorithm

Given an array of integers, sort it using quick sort algorithm.


 
Quicksort is an efficient in-place sorting algorithm and can be about two or three times faster than its main competitors, merge sort and heapsort when implemented well. Quicksort is a comparison sort, meaning that it can sort items of any type for which a less-than relation is defined. In efficient implementations, it is usually not a stable sort.

Quicksort on average takes O(n log(n)) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is very rare.

 

How Quicksort works?

Quicksort is a divide and conquer algorithm. Like all divide and conquer algorithms, quicksort first divides a large array into two smaller sub-arrays and then recursively sort the sub-arrays. Basically, three steps are involved in whole process –

  • Pivot selection: Pick an element, called a pivot, from the array (usually the leftmost or the rightmost element of the partition).
     
  • Partitioning: Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position.
     
  • Recurse: Recursively apply the above steps to the sub-array of elements with smaller values than pivot and separately to the sub-array of elements with greater values than pivot.
     

The base case of the recursion is arrays of size 1, which never need to be sorted.

Below diagram shows how at each step of the quicksort algortihm we choose leftmost element as pivot, parition the array across pivot and recuse on two sub-arrays we get after partition process.

  quicksort
 

IMPORTANT NOTE – The pivot selection and partitioning steps can be done in several different ways and the choice of specific implementation schemes greatly affects the algorithm’s performance. We will discuss all that in detail later, but let’s now get to the coding part.

 
Recursive C++ implementation –
 

Download   Run Code

Output:

-6 -3 1 2 3 5 6 8 9

 

Performance:

Worst case time complexity of Quicksort is O(n2). The worst case happens when the pivot happens to be the smallest or largest element in the list, or when all the elements of array are equal. This will result in most unbalanced partition as the pivot divides the array into two sub-array of sizes 0 and n – 1. If this happens repeatedly in every partition (example, we have sorted array), then each recursive call processes a list of size one less than the previous list and that will result in O(n²) time.

T(n) = T(n-1) + cn = O(n²)

(Note – partition takes O(n) time that accounts for cn)

Best case time complexity of quick sort is O(nlog(n)). The best case happens when the pivot divides the array into two nearly equal pieces. Now each recursive call processes a list of half the size.

T(n) = 2 T(n/2) + cn = O(n log(n))

 

How to Boost performance?

Quicksort performance can be boosted in several ways. We will try to cover few of them –

1. Better pivot selection

Quicksort normally choose the leftmost or the rightmost element of the partition as the pivot element. This selection will cause worst-case behavior on already sorted arrays. The problem can be easily solved by choosing either a random index for the pivot (called Randomized Quicksort) or choosing the median of the first, middle and last element of the partition for the pivot. Randomized partition implementation can be seen here.

2. Hoare’s Partitioning scheme

Hoare partition scheme uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot, one smaller, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index.

Hoare’s scheme is more efficient than partitioning logic used above (also called as Lomuto’s partition scheme) because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal. We will soon discuss this approach in a separate post.

3. Handle Repeated elements

With a partitioning algorithm such as the ones described above (even with one that chooses good pivot values), quicksort exhibits poor performance for inputs that contain many repeated elements. The problem is clearly visible when all the input elements are equal. Then at each recursion, the left partition is empty (no input values are less than the pivot), and the right partition has only decreased by one element (the pivot is removed). Consequently, the algorithm takes quadratic time to sort an array of equal values.

To solve this problem (sometimes called the Dutch national flag problem), an alternative linear-time partition routine can be used that separates the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot. The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted.

The best case for the algorithm now occurs when all elements are equal (or are chosen from a small set of k « n elements). In the case of all equal elements, the modified quicksort will perform at most two recursive calls on empty subarrays and thus finish in linear time. This approach is discussed here.

4. Using Tail Recursion

To make sure at most O(log(n)) space is used, recurse first into the smaller side of the partition, then use a tail call to recurse into the other. As such, we successfully sort the array in a way that it minimizes the recursive depth. It’s implementation can be seen here.

5. Hybrid with Insertion Sort

When the number of elements is below some threshold (perhaps ten elements), switch to a non-recursive sorting algorithm such as insertion sort that performs fewer swaps, comparisons or other operations on such small arrays. This approach is discussed here.

Instead of “many small sorts” optimization, when the number of elements is less than some threshold k, we can simply stop. Later when the whole array has been processed, each element will be at most k positions away from its final sorted position. Now if we perform insertion sort on it, it will take O(kn) time to finish the sort, which is linear as k is a constant.

 
References:
https://en.wikipedia.org/wiki/Quicksort

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂