Quick Sort

Quicksort is a sorting algorithm that sorts an array based on the principle that an element is sorted if all the elements before it are smaller than it, and all the elements after it are greater than it. This process, known as partitioning is applied recursively in an array, until the entire array is sorted.

Process §

1. Take an array, 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.
2. To do this, take two pointers (usually i and j ). Start i from the left and j from the right.
3. Increase i and decrease j until A[i] is greater than pivot, and A[j] is smaller than pivot. Basically, these two elements are both in the wrong position. So swap them.
4. Continue this process, swapping any elements in the ‘wrong’ place.
5. STOP when i = j. As this means we’ve gone through the entire array. Now we just ‘insert’ the pivot element here by swapping A[i] with A[pivot]
6. The pivot element has been successfully sorted, or partitioned. Now recursively repeat steps 1-5 on the 2 subarrays to the left and right of the pivot,

Pseudocode §

def Quicksort(A, min, max): #min and max are the 'bounds' for the partition operation
	p ← int 
	If min < max then:
		p ← partition(A,min,max)
		#Recursive calls
		Quicksort(A,min,p-1)
		Quicksort(A,p+1,max)

def partition(A,min,max):
	pivot ← Random pivot index in A
	pivotVal ← A[pivot]
		#To keep things simple, we can avoid the pointers checking the pivot by putting it at the end
	Swap A[pivot] with A[max] 
	pivIndex ← min
	For i from min to max do:
		If A[i] < pivotVal then:
			Swap A[i] with A[pivIndex]
			pivIndex ← pivIndex + 1
	Swap A[pivIndex] with A[max]
	return pivIndex

Complexity Analysis §

Time Complexity: $O(n^2)$ , $\Omega (n\log n)$ §

The worst case for quicksort is if the ‘pivot’ is placed such 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)$ (partitioning the the array ) + $c\ast n$ (work done on the 1-sized array)

$T(n)=T(n-1)+cn$ $T(2)=T(1)+2c$ $T(3)=T(2)+3c=T(1)+2c+3c=T(1)+5c$ $T(4)=T(3)+4c=T(2)+\cdots +4c=T(1)+9c$ $\dots T(n)=T(1)+(n+(n-1)+(n-2)+\cdots +2)c$ $T(n)=T(1)+\frac{n(n-1)}{2}\ast c$ (Sum of natural numbers)

$=O(n^2)$

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

$\Omega (n\log n)$

Implementation §

quicksort.py