# Quick Sort

Sorting algorithm that is prevalent in practice. Although it has the same runtime on average as merge sort, it will execute faster due to reduced memory requirements. Additionally, it is far easier to implement than quick sort.

One important consideration is the implementation of Choose Pivot. Choosing a pivot element that represents the median value in the array is ideal. However, the overhead associated with calculating the median renders the approach ineffective. There are mathematical proofs that demonstrate choosing a pivot point at random will ensure O(n log(2, n)) on average.

## Asymptotic Complexity

$O(n \lg_{2}n)$ on average

## Pseudo Code

sort:
// side effect: rearranges the values in A
A = input array
n = length of A

if n <= 1:
return

pivot = choose_pivot(n)
swap A and A[pivot]

pivot_index = partition(A)

// The array is never copied, all swaps happen in place.
// Recursive calls pass a reference to a portion of the array.
sort(A[0 thru pivot_index - 1])
sort(A[pivot_index + 1 thru n])

partition:
// side effects:
// - All items in A that are less than the value at A are before A[return value]
// - All items in A that are greater than the value at A are moved after A[return value]
// - The value at A is moved to A[return value]
// Assumption: A is the value to partition aroundk
returns: new position of the value at A after the partition
A = input array
n = number of elements to partition around

index = 1
for i = 1 to n:
if A[i] < A:
swap A[i] and A[index]
increment index

if index - 1 > 0:
swap A and A[index]

return index

choose_pivot:
returns: ideal index to partition on
n = number of elements in the partition

return uniformly random number between 0 and n inclusive


Full Repo

Relevant Files: