Quick Sort

Quicksort is a divide-and-conquer sorting algorithm that partitions an array by using a single element, known as a pivot and sorts it. This partitioning process is applied recursively.

An element is considered sorted if all the elements smaller than it are to the left, and all the elements greater than it are to the right of it.

Process §

Quicksort’s performance depends on the type of partitioning done.

• Hoare Partitioning: A single element is selected a pivot, usually randomly. In some cases it can be the first or last element.

1. Take an array, $A[0\dots n-1]$ and select a pivot. This pivot is the element in the array that we want to be sorted, by moving all smaller elements to the left, and all bigger elements to the right. Let the index of this pivot element be $p$
2. To do this, take two pointers $i=0$ and $j=n-1$. These are our ‘left’ and ‘right’ pointers.
3. Repeat until $i=j$
   1. Increase $i$ and decrease $j$ until $A[i]>A[p]$ (the element at index $i$ is greater than the pivot) and $A[j]<A[p]$ (the element at index $j$ is smaller than the pivot). Basically, these two elements are both in the wrong position.
   2. Swap $A[i]$ and $A[j]$
   3. Continue this process, swapping any elements in the ‘wrong’ place.
4. Once $i=j$, we have gone through the entire array.
5. Insert the pivot by swapping $A[i]$ and $A[p]$
6. The pivot element has been successfully sorted, or partitioned.
7. Now recursively repeat steps 1-6 on the 2 subarrays $A_L[0\dots p-1]$ and $A_R[p+1\dots n]$

Pseudocode §

Algorithm Quicksort(A: Array, min, max): #min and max are the 'bounds' for the partition operation

	//Hoare Partitioning
	Function Partition(A,min,max):
		piv <- min
		i <- min; j <- max
		Do:
			While i < max and A[i] <= p do:
				i <- i + 1
			End do
			While j >= min and A[j] > p do:
				j <- j - 1
			End do
			A[i] <-> A[j]
		While i < j
		//Undo last swap
		A[i] <-> A[j] 
		//Insert pivot into correct position
		A[p] <-> A[j]
		Return j
	End Function

	p ← 0
	If min < max then:
		p ← Partition(A,min,max)
		//Recursive Calls
		Quicksort(A,min,p-1)
		Quicksort(A,p+1,max)
	End if
End Algorithm

Properties §

• In-place
• Unstable

Time Complexity §

Case Scenario	Input Description	Growth Function	Big-O	Notes
Worst	Array is already sorted	$T(n)=T(n-1)+n$ $T(1)=T(0)=0$	$\Theta (n^2)$	The partitioning results in no left subarray, and a right subarray of size $n-1$. The growth function can seen as a summation of ${\sum }_{i=2}^{n}i$, which equates to the triangular numbers formula $n(n+1)/2$
Average
Best	Pivot is median	$T(n)=2T(\frac{n}{2})+n$ $T(1)=T(0)=0$	$\Theta (n\log (n))$	Identical to merge sort

Worst Case §

The worst case for quicksort is if the ‘pivot’ is placed such a way that it divides an $n$ array into 1 and $(n-1)$ sized arrays. In which the case recurrence relation will be:

$$T(n)=T(n-1)+n$$

This shows that the algorithm would degenerate from a divide-and-conquer (splitting problem by a constant division) to a decrease-and-conquer algorithm (since the problem is reduced by 1 each step)

Solving by Iteration

Solving $T(n)=T(n-1)+n$ $T(1)=0$ $T(2)=0+2$ $T(3)=T(2)+3=0+2+3=5$ $T(n)={\sum }_{i=2}^{n}i=n(n+1)/2-1\in \Theta (n^2)$

Hence the worst case is:

$$\Theta (n^2)$$

Best Case §

The best case is when quicksort partitions the array into 2 equal subsections, in which case it behaves identically to merge sort, resulting in a time complexity of:

$$\Theta (n\log (n))$$

Average Case §

Roughly $2\ln (n)$ recursive calls

Modifications §

Random Partitioning §

Picking a random pivot from $min$ to $max$ reduces the likelihood of the worst-case scenario (where the pivot reduces the array instead of splitting it)

Median-of-three Partitioning §

A simple approximation of random partitioning is by finding the middle (median) of three candidates, $A[min]$, $A[max]$ and $A[\frac{max+min}{2}]$ By setting the pivot to the median, and then swapping the values such that the largest of the three is swapped with $A[max]$ .

Then, the pseudocode is simplified:

Algorithm Quicksort(A: Array, min, max): #min and max are the 'bounds' for the partition operation
	//Median-of-three Partitioning
	Function Partition(A,min,max):
		piv <- Median
		i <- min; j <- ma
		Do:
			While i < max and A[i] <= p do:
				i <- i + 1
			End do
			While j >= min and A[j] > p do:
				j <- j - 1
			End do
		While i < j
		//Undo last swap
		A[i] <-> A[j] 
		//Insert pivot into correct position
		A[p] <-> A[j]
		Return j
	End Function

	p ← 0
	If min < max then:
		p ← Partition(A,min,max)
		//Recursive Calls
		Quicksort(A,min,p-1)
		Quicksort(A,p+1,max)
	End if
End Algorithm

Combine with Insertion Sort §

When there are very few elements left, insertion sort can be used for faster performance

Algorithm Sort(A[lo..hi]):

	Function QuickAlmostSort(A[lo..hi])
		If lo + 10 < hi then:
			s ← Partition(A[lo..hi])
			QuickAlmostsort(A[lo..s − 1])
			QuickAlmostsort(A[s + 1..hi])
		end if
	end Function

	QuickAlmostsort(A[lo..hi])
	InsertionSort(A[lo..hi])
End Algorithm

Implementation §