Asked In: Google, Microsoft, Adobe, SAP Labs, Goldman Sachs, Qualcomm

Why quicksort?

Quick sort is one of the most popular sorting algorithms, which uses the divide-and-conquer problem-solving approach. There are several reasons to learn this algorithm:

• One of the best algorithms for learning the idea of recursion.
• Quicksort is often the best practical choice for sorting because it works efficiently on average O(nlogn) time complexity.
• One of the best algorithms to learn the idea of worst, best, and average-case analysis of an algorithm.
• The partition process of quick sort is an excellent algorithm for learning the two-pointers approach. We can use similar ideas to solve several other DSA questions.
• One of the best algorithms to understand efficient problem-solving using randomization.

Idea behind quicksort

Suppose we divide an unsorted array into two halves around some value X[i] in the array such that:

• Elements in the left half are less than X[i].
• Elements in the right half are greater than X[i].

If we sort we sort both halves, our whole array gets sorted because after partition, X[i] gets placed at the correct position of the sorted output. Here both unsorted halves are a similar sorting problem but for smaller input sizes (smaller sub-problems). So we can use the idea of recursion and sort both halves recursively using the same sorting method.

This idea is based on the divide and conquers method of problem-solving, where we divide the problem into smaller subproblems and solve each sub-problems recursively to get the final sorted array.

Quick sort divide and conquer idea

Divide step: Divide the problem into smaller sub-problems by partitioning X[l…r] into two smaller subarrays around some pivot element. To do this, we use a partition method inside the quick sort function, which returns the pIndex (index of the pivot after the partition).

• Subproblem 1: Sort X[] from l to pIndex — 1.
• Subproblem 2: Sort X[] from pIndex + 1 to r.

Conquer step: Sort both halves recursively.

Combine step: After the conquer step, our whole array will get sorted. So there is no need to perform the combine step.

Quicksort implementation

Suppose the function call quickSort(X[], l, r) sorts the entire array where l and r are the left and right ends.

Divide: We define partition(X, l, r) function inside quickSort() method to divide array around a pivot. By the end of this method, we return the index of the pivot i.e. pIndex = partition(X, l, r)

Conquer: We recursively call quickSort(X, l, pIndex — 1) to sort the left half and recursively call quickSort(X, pIndex + 1, r) to sort the right half.

Base case: If we find l≥r during the recursive calls, the sub-array is either empty or has one value left. Our recursion should not go further and return from here.

Quicksort pseudocode

Partition algorithm quick sort

Now, how can we divide array around pivot so that elements in the left half are less than the pivot and elements in the right half are greater than the pivot? Is it feasible to do it in place? Think!

Suppose we pick pivot = X[r] and scan the array from left to right. Whenever we find some X[i] less than the pivot, we place it in the starting part of the array. Otherwise, we ignore X[i]. For this, we need two pointers to track two parts: The pointer i to track the current index and the pointer j to track the starting subarray (from 0 to j) where values are less than pivot. At the start j = l — 1 and i = l.

Now we traverse array from i = l to r — 1. When X[i] < pivot, we increment j and swap X[i] with X[j]. Otherwise, we ignore X[i] and move forward to the next element. This loop will terminate when i = r.

After the loop, values in subarray X[0…j] will be less than the pivot, and values in subarray X[j…r — 1] will be greater than the pivot. So we swap the pivot (X[r]) with X[j + 1] to complete the partition process because the correct position of the pivot will be index j + 1.

By the end of the partition process, we return index j + 1.

Pseudocode of partition algorithm

Visualization of partition algorithm

Analysis of the partition algorithm

We are running a single loop and doing constant operations at each iteration. So, time complexity = O(n). We are using constant extra space, so space complexity = O(1).

Quicksort visualisation

Analysis of the quicksort

We first need to define the recurrence relation to analyse the recursive function. Suppose T(n) is the time complexity of quicksort for input size n. To get the expression for T(n), we add the time complexities of each step in the above recursive code:

Divide step: The time complexity of this step is equal to the time complexity of the partition algorithm i.e. O(n).

Conquer step: We solve two subproblems recursively, where subproblem size will depend on the value of the pivot during partition algorithm. Suppose i elements are on the left of the pivot and n — i — 1 elements are on the right of the pivot after partition.

• Input size of left subarray = i
• Input size of right subarray = n — i — 1

Conquer step time complexity = Time complexity to sort left subarray recursively + Time complexity to sort right subarray recursively = T(i) + T(n — i — 1)

Combine step: This is a trivial step and there is no operation in the combine part of quick sort. So time complexity of combine step = O(1).

T(n) = O(n) + T(i) + T(n — i — 1) + O(1)

= T(i) + T(n — i — 1) + O(n)

= T(i) + T(n — i — 1) + cn

Recurrence relation of the quick sort:

• T(n) = c, if n = 1
• T(n) = T(i) + T(n — i — 1) + cn, if n > 1

Worst-case time complexity analysis of the quick sort

Quick sort worst-case occurs when pivot is always the largest or smallest element during each call of partition algorithm. In such a situation, partition process is highly unbalanced, where one subarray has n — 1 element and the other subarray is empty. Note: Worst case always occurs in the case of sorted or revere sorted array. Think!

So, for calculating quick sort time complexity in the worst case, we put i = n — 1 in the above equation of T(n) => T(n) = T(n — 1) + T(0) + cn = T(n — 1) + cn

Analysis using the recursion tree method

In this method, we draw the recursion tree and sum the partitioning cost for each level => cn + c(n−1) + c(n−2) +⋯+ 2c + c ​= c (n + n−1 + n−2 + ⋯+ 2 + 1) = c(n(n+1)/2) = O(n²). So worst case time complexity of quick sort is O(n²).

Best case time complexity analysis of the quick sort

Quick sort best case occurs when the pivot is always the median element during each call of the partition algorithm. In such a situation, the partition process is balanced and the size of each sub-problems is approx. n/2 size.

So, for calculating quick sort time complexity in the best case, we put i = n/2 in the above equation of T(n) => T(n) = T(n — 1) + T(0) + cn = T(n — 1) + cn

So for the time complexity in the best case, we put i = n/2 in the above equation of T(n) => T(n) = T(n/2) + T(n — 1 — n/2) + cn = T(n/2) + T(n/2 — 1) + cn ~ 2 T(n/2)+ cn

This is similar to the recurrence relation of merge sort. So we can solve this using both the recursion tree method and the master theorem. In other words, the best-case time complexity of quick sort is equal to the time complexity of merge sort which is O(nlogn).

Here is the recursion tree diagram for the best case of quick sort.

Average case time complexity analysis of the quick sort

When we select pivot randomly during the partition process, partitioning is highly unlikely to happen in the same way at every level, i.e. some of the splits will be close to a balanced scenario, and some will be close to an unbalanced scenario. In such a practical scenario, an average case analysis of quick sort will give us a better picture. Note: Here, we assume that the probability of choosing each element as the pivot is equally likely.

In the average case, the partition process will generate a combination of good (balanced partition) and bad (unbalanced partition) splits, where good and bad splits will be distributed randomly in the recursion tree.

Suppose at the first level of the recursion tree, the partition process creates a good split, and at the next level, the partition generates a bad split. So the combined cost of the partition process at both levels will be O(n). In other words, the combination of an unbalanced partition followed by a balanced partition will take O(n) partitioning time. This looks similar to the scenario of a balanced partition!

So the average-case time complexity of quicksort will be closer to the best-case time complexity O(nlogn). For better understanding, suppose the partition algorithm always generates a partially unbalanced spit in the ratio of 9 to 1.

Recurrence relation: T(n) = T(9n/10) + T(n/10) + cn.

The following diagram shows the recursion tree for this recurrence.

Image source: CLRS Book

We can notice the following things from the above diagram:

• The left part of the recursion tree is decreasing fast with a factor of 1/10 and the right part is decreasing slowly with a factor of 9/10. So in the worst case, the maximum depth of the recursion tree will be equal to log10/9(n), which is O(logn).
• The partitioning cost is at most cn at every level of the recursion tree. After doing level by level sum, the total cost of the quick sort will be cn*O(logn) = O(nlogn). So for an unbalanced split of 9-to-1, quicksort works in O(nlogn) time complexity.
• In general, time complexity will be O(nlogn) whenever split has constant proportionality. For example, 99-to-1 split will also produce O(nlogn) time complexity for quick sort.

Space complexity analysis of quick sort

We are not using additional extra space inside the recursive code, so quicksort is an in-place sorting algorithm. But in the background, every recursive program uses call stack. So space complexity will depend on the call stack size, which is equal to the height of the recursion tree!

In the quick sort algorithm, the height of the recursion tree will depend on the choice of pivot during the partition process. When the partition is always unbalanced (worst case scenario), the input size of the recursion will decrease by 1 at each level, or there is only one node at each level of the recursion tree. In such a situation, the height of the recursion tree will be O(n), and the compiler will allocate a call stack of size O(n). So space complexity of quick sort in the worst-case = O(n).

When the partition is always balanced (best-case scenario), the input size of recursion will decrease by a factor of 1/2 at each level. In such a scenario, the height of the recursion tree will be O(logn), and the compiler will allocate a call stack of size O(logn). So space complexity of quick sort in the best-case = O(logn)

Various ways to choose pivot

• Selecting the rightmost element of array as a pivot.
• Selecting the leftmost element of array as a pivot.
• Selecting a pivot randomly from all array elements
• Selecting median of first, last and middle element as a pivot.

Choosing rightmost or leftmost element as the pivot element can lead to worst-case scenario when an array is sorted or reverse sorted. So one the best idea is to choose pivot randomly, which minimizes the situation of worst-case. If we definitely want to avoid the worst case situation, selecting median element as a pivot would also be acceptable in the majority of cases.

Pseudocode for the median-of-three pivot selection:

mid = l + (r - l)/ 2
if X[mid] < X[l]
    swap (X[l], X[mid])
if X[hi] < X[lo]
    swap (X[l], X[r])
if X[mid] < X[r]
    swap (X[mid], X[r])
pivot = X[r]

Critical ideas to think!

• How can we modify quicksort to sort an array into non-increasing order?
• How can we improve the time complexity of quicksort using insertion sort? Hint: Insertion sort works in O(n) time when input is sorted or almost sorted.
• Does the above implementation of quicksort stable? If not, how can we modify it to make it stable?
• What would be the average space complexity of the quick sort? How can we optimize the space complexity to O(logn) in the worst case?
• How can we implement quicksort iteratively using stack?
• How we modify above quick sort code to handle repeated elements?
• Why do we prefer quick sort over merge sort for sorting arrays?
• Why do we prefer merge sort over quick sort for sorting linked lists?
• How is quick sort similar to tree sort or BST sort?

Similar concepts to explore further

• The idea of Hoare Partition
• Linear time sorting algorithms like counting sort and bucket sort
• Comparison of sorting algorithms
• Lower bound of comparison sorting
• Why sorting algorithms?
• Implementation and Analysis of Randomised quick sort
• Quicksort optimization using the tail recursion approach

Coding problems to practice

• Dutch National Flag Problem
• QuickSelect approach — kth smallest element in an array
• Move all the zeroes to the end
• Fuzzy sorting of intervals
• Find first missing positive in an array
• Remove duplicate elements from sorted array
• Median of two sorted arrays of the same size

Content References

• Algorithms by CLRS
• The Algorithm Design Manual by Steven Skiena

For more content, explore our free DSA course and coding interview blogs.

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!