Foundations‎ > ‎Algorithms‎ > ‎Sorting‎ > ‎

Quicksort

- Time Complexity -

O(n2)

- Pseudocode -

QUICKSORT(A, p, r)
1  if p < r
2    then q ← PARTITION(A, p, r)
3      QUICKSORT(A, p, q - 1)
4      QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)
1  x ← A[r]
2  i  ←  p - 1
3  for j ← p to r - 1
4    do if A[j] ≤ x
5      then i ← i + 1
6        exchange A[i] ↔ A[j]
7  exchange A[i + 1] ↔ A[r]
8  return i + 1