Quick Sort

by codecrucks · Published 11/09/2021 · Updated 08/06/2022

Quick sort was invented by Tony Hoare. It is a divide and conquer strategy. Quicksort is sometimes referred to as partition exchange sort.

Quick sort picks one element as a pivot and shifts the pivot to the correct location in each iteration. By repositioning the pivot, the list is divided into two sublists of equal or unequal size.

Each sublist is solved in a recursive manner. In contrast to merge sort, the list is partitioned dynamically in this case. Merge sort partitions an array based on its position, whereas quicksort partitions it based on its actual value.

Merge sort splits the list from the center, but quicksort does not guarantee such balanced division. The value of the pivot, not the position, determines division. As a pivot, the first, last, or any random element can be chosen. However, the pivot position should remain constant throughout all the recursive calls.

Each sublist represents a new problem with a size smaller than n. A new pivot is chosen, and the procedure is repeated until it reaches the base case (i.e. list of size 1).

Algorithm

Algorithm for quicksort is shown below

Algorithm QUICKSORT (A, low, high)
// Description : Sort array A using Quicksort
// Input : Unsorted array A of size n, low = 0, high = n - 1
// Output : Sorted array A

if low ≤ high then
  q ← PARTITION (a, low, high)	
  QUICKSORT (A, low, q – 1)	
  QUICKSORT (A, q + 1, high)	
end

Subroutine PARTITION determines the correct position of pivot in a sorted array. The function PARTITION traverses the array from left to right. It detects elements bigger than the pivot using the low pointer, and elements less or equal to the pivot using the high pointer. The pseudo code of PARTITION subroutine is given below:

PARTITION (A, low, high)
x ← A[high]	// x is pivot element i.e. last element of list
i ← low – 1	 
for j ← low to high – 1 do
  if A[j] ≤ x then
    i ← i + 1
    swap (A[i], A[j])
  end
end
swap (A[i + 1], A[high])
return (i + 1)	// Correct index of pivot after sorting

On each recursive call, quick sort does following:

Procedure Scan array from left to right until an element greater than pivot is found.
Scan array from right to left until an element equal or smaller than pivot is found.
After finding such elements,
- If low < high, then exchange A[low] and A[high].
- If low ≥ high, then exchange A[pivot] and A[high], which will split the list into two sub-lists. Solve them recursively.

Example of Quick Sort

Problem: Trace quick-sort for the data set A = {44, 22, 33, 77, 11, 55, 66}

Solution:

According to its working principle, quick sort algorithm finds the element larger than pivot while moving from left to right, and finds element smaller than or equal to pivot while moving from right to left. When such elements are found,

If low < high, exchange A[low] and A [high].
If low ³ high, exchange A[pivot] and A[high]. This will split the list into two sub-lists and both sub-lists are sorted recursively.

Simulation of the quicksort for given data is shown below:

Step 1: Fix pivot point, low and high pointers.

Keep moving low and high pointer until A[low] > A[pivot] and A[high] ≤ A[pivot]. And if

low < high then swap A[low] and A[high]
low ≥ high then swap A[pivot] and A[high]

Step 2: A[low] = 22 and A[pivot] = 44

A[low] < A[pivot] ⇒ low = low + 1 = 1 + 1 = 2

Step 3: A[low] = 33 and A[pivot] = 44

A[low] < A[pivot] ⇒ low = low + 1 = 2 + 1 = 3

Step 4: A[low] = 77 and A[pivot] = 44

A[low] > A[pivot] ⇒ fix low check for high pointer

A[high] = 66 and A[pivot] = 44

A[high > A[pivot] ⇒ high = high – 1 = 6 – 1 = 5

Step 5: A[high] = 55 and A[pivot] = 44

A[high] > A[pivot] ⇒ high = high – 1 = 5 – 1 = 4

Step 6: A[high] = 11 and A[pivot] = 44

A[high] ≤ A[pivot] ⇒ fix high and perform swap

Here, low < high, so swap A[low] with A[high] and again start moving low pointer

Step 7: A[low] = 11 and A[pivot] = 44

A[low] < A[pivot] ⇒ low = low + 1 = 3 + 1 = 4

Step 8: A[low] = 77 and A[pivot] = 44

A[low] > A[pivot] ⇒ fix low and check high

A[high] = 77 and A[pivot] = 44

A[high] > A[pivot] ⇒ high = high – 1 = 4 – 1 = 3

Step 9: A[high] = 11 and A[pivot] = 44

A[high] ≥ A[pivot] ⇒ fix high and perform swap

Here, low ≥ high so swap A[pivot] with A[high] divide list in two sublists and reset pointers. Recursively sort both the sublists.

Step 10: Let us first sort the left sub-list

A[low] = 22 and A[pivot] = 11

A[low] > A[pivot], so fix low and check high pointer

A[high] = 33 and A[pivot] = 11

A[high] > A[pivot] ⇒ high = high – 1 = 2 – 1 = 1

Step 11: A[high] = 22 and A[pivot] = 11

A[high] > A[pivot] ⇒ high = high – 1 = 1 – 1 = 0

Step 12: A[high] = 11 and A[pivot] = 11

A[high] ≤ A[pivot] ⇒ so fix high and perform swap

Here, low ≥ high so swap A[pivot] with A[high], divide list in two sublists and reset pointers. Recursively sort both the sublists

Step 13 : A[low] = 33 and A[pivot] = 22

A[low] > A[pivot] Þ so fix low and check high pointer

A[high] = 33 and A[pivot] = 22

A[right] > A[pivot] ⇒ high = high – 1 = 2 – 1 = 1

Step 14: A[high] = 22 and A[pivot] = 22

A[high] ≤ A[pivot], so fix high and perform a swap

Here, low ≥ high so swap A[pivot] with A[high], divide list in two sub-lists. Left sub-list has size zero and right sub-list has only one element {33}, so no further process is required.

Step 15: Let us now sort the right sub-list of original array derived in step 9

A[low] = 55 and A[pivot] = 77

A[low] < A[pivot] ⇒ low = low + 1 = 5 + 1 = 6

Step 16: A[low] = 66 and A[pivot] = 77

A[low] < A[pivot] ⇒ low = low + 1 = 6 + 1 = 7

low > high so stop, and check for high index

A[high] = 66 and A[pivot] = 77

A[high] < A[pivot], so fix high and perform swap

Here, low ≥ high so swap A[pivot] with A[high], divide list in two sub lists and reset pointers. Right sub list has size zero. So only left sub list needs to be sorted

Step 17: A[low] = 55 and A[pivot] = 66

A[low] < A[pivot] ⇒ low = low + 1 = 5 + 1 = 6

low > high so stop, and check for high index

A[high] = 55 and A[pivot] = 66

A[high] < A[pivot], so fix high and perform swap Here, low ≥ high so swap A[pivot] with A[high], divide list in two sub lists and reset pointers. Right sub list has size zero and right sub list is of size 1, so sorting is not required at all.

The final sorted array is :

Complexity Analysis of Quick Sort

Best Case:

Best case for quicksort occurs when the list is divided from the middle. Partitions are balanced and it is identical to merge sort. Hence the complexity of the best case will be O( n log₂ n). Let us prove it by solving the recurrence equation.

T(1) = 0

T(n) = 2T(n/2) + O(n) …(1)

2T(n/2) is the time required to solve two problems of size (n/2)

O(n) is the time required to fix the position of the pivot. Fixing of pivot requires a scan of the entire array.

The recurrence of the quicksort for the best case is identical to the recurrence of merge sort.

Depending upon how partitioning is done, running time of quick sort varies form O(nlog₂n) to O(n²). Best and worst case partitioning is shown in following diagram. Best case occurs when partitioning happens from the center of list on each call. In this case, quick sort resembles to merge sort. Worst case occurs when list is already sorted. In this case, on subsist will be of size 0, and other will be always of size (n – 1)

We will derive the time complexity of merge sort using two methods:

Substitution method
Master method

Substitution Method:

Solving original recurrence for n/2,

T(n/2) = 2T(n/4) + n/2

Substituting this in equation (1),

T(n) = 2[ 2T(n/4) + n/2 ] + n

= 2² T(n/2²) + 2n

After k substitutions,

T(n) = 2^k T(n/2^k) + k.n … (2)

Division of array creates binary tree, which has height log₂n, so let us consider that k grows up to log₂n,

k = log₂n ⇒ n = 2^k

Substitute these values in equation (2)

T(n) = nT(n/n) + log₂n . n

T(n) = O(n.log₂n) (because, T(1) = 0, from base case)

Master Method:

Recurrence of the merge sort, T(n) = 2T(n/2) + n is of the form T(n) = a.T(n/b) + f(n),

Comparing both the recurrence,

a = 2, b = 2 and f(n) = n with d = 1, where d is the degree of polynomial function f(n).

b^d = 2¹ = 2 Here, a = b^d, so from the Case 1 of Variant – I of master method,

T(n) = O(n^dlog₂n)

= O(nlog₂n)

Worst Case:

The worst case scenario for quicksort is when the list has already been sorted. The pivot will be at either end in such scenario. Quick sort’s worst-case behavior generates subproblems with (n – 1) elements and zero elements. Following figure depicts the worst-case division of the list. In this scenario, the tree’s height would be n.

Because each call sets the right position of the pivot and no further work is required, the combination cost for quicksort is constant. The method scans the array and identifies the right location of the pivot to split the list, therefore the division cost of QUICK SORT is linear, i.e. O(n). In the worst-case scenario, one of the sublists has size 0 and the other has size (n – 1), thus the algorithm must solve a problem of size (n – 1) in the subsequent recursive call.

Thus,

T(0) = 1 (Base case)

T(n) = T(conquer) + T(divide) + T(combine)

T (n) = T (n – 1) + O(n) + Q(1)

= T (n – 1) + n …(1)

Using iterative approach,

Substitute n by (n – 1) in Equation (1),

T (n – 1) = T (n – 2) + (n – 1) …(2)

⇒ T (n) = T (n – 2) + (n – 1) + n …(3)

Substitute n by (n – 1) in Equation (2),

T (n – 2) = T (n – 3) + (n – 2)

From Equation (3),

T (n) = T (n – 3) + (n – 2) + (n – 1) + n

∶ ∶

After k iterations,

T(n) = T(n – k) + (n – k + 1) + (n – k + 2) + … + (n – 1) + n

Let k = n,

T (n) = T (0) + 1 + 2 + 3 + . . . + (n – 2) + (n – 1) + n

= 1 + 2 + 3 + …+ n = S n

= n(n + 1) / 2

= (n²/2) + (n/2)

= O(n²)

Note : In the worst case, quick sort behaves similar to selection sort.

Average case:

For quick sort, average-case running time is much closer to the best case.

That is, T (n) = O(n log₂n)

The time complexity of all three cases is stated in the following table:

Best case	Average case	Worst case
O(nlog₂n)	O(nlog₂n)	O(n²)

Simulation of Quick Sort

Image Source: https://commons.wikimedia.org/wiki/File:Quicksort-example.gif [Wiki]

Properties of Quick Sort

In place : It uses O(log n) amount of extra memory.
Quicksort is massively recursive.
In the best case, quicksort is extremely fast.
It is very complex.

Randomized Quick Sort

The worst-case scenario for quicksort is determined by how we choose a pivot element. The worst case scenario for quicksort is when the array has already been sorted and the first or last member is used as a pivot. To improve performance, we can add randomization to an algorithm.

In the worst-case scenario, choosing the first or last element as the pivot splits lists into (n – 1) and 0 size sub-lists. Partitions can be approximately balanced by using a random element as a pivot, and performance near to merging sort may be attained. The position of the pivot point is an important component in the performance of a quick sort.

Few choices for pivot selection:

Select middle element of the list as a pivot.
Select random element from the list as a pivot.
Use median as a pivot.

Discussion and Comparison

Despite the fact that quicksort’s worst-case running time is O(n²), it is regarded superior than merge sort for a variety of reasons. The sorting algorithm’s complexity is assessed by the number of comparison operations done by the algorithm. Quick sort performs fewer comparisons than merge sort. Quicksort is in-place algorithm that takes up O(log₂n) addition space. Where as, merge sort requires O(n) additional space. Quicksort also has high cache locality, reducing the amount of memory accesses. Furthermore, by providing a randomized variant, the worst-case running time of quicksort can be reduced to O(nlog₂n).

Merge Sort vs. Quick Sort

Sr. No	Merge sort	Quicksort
1.	Partitioning is always balanced	Partitioning may not be balanced
2.	Worst-case running time is O(nlog₂n)	Worst-case running time is O(n²)
3.	It is not in place sorting method	It is in place sorting method
4.	Recurrence for worst-case: T(n) = 2T(n/2) + n	Recurrence for worst-case: T(n) = T(n – 1) + n
5.	Merge sort is not adaptive	Quicksort is adaptive
6.	Does more comparison in the best case compared to quicksort	Does less comparison in the best case compared to merge sort

Quicksort performs worst when the data set is already sorted. Running time of quicksort in the worst case is O(n²), whereas merge sort runs in O(nlog₂n) time in all three cases.
For data set S = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} worst-case running time of quicksort and merge sort would be different.
For data set S = {0, 7, 2, 8, 1, 3, 9, 5, 4, 6}, both runs in O(nlog₂n) time, but compare to merge sort, quick sort does less comparisons.

Some Popular Sorting Algorithms

Following are the few popular sorting algorithms used in computer science: