Quicksort

page=255

Quicksort is an In-Place Algorithm, which has very bad runtime if the array is sorted or nearly sorted.

Runtime

Worst case running time of $\Theta (n^2)$ Average case running time of $\Theta (n\ast lg(n))$

Function

Uses the Partition function, and recursively calls itself until the array is sorted.

• A - table
• p - left
• r - right
• x - pivot

def QUICKSORT(A, p, r):
	if p < r:
		#Partition the subarray around the pivot, which ends up in A[q]
		q = PARTITION(A, p, r)
		QUICKSORT(A, p, q-1) #recursively sort the low side
		QUICKSORT(A, q+1, r) #recursively sort the high side
	return A