Quick Sort

Quick Sort

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O (n log n) comparisons to sort n items. In the worst case, it makes O (n²) comparisons, though this behaviour is rare. Quicksort is often faster in practice than other O (n log n) algorithms.^[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort is a comparison and, in efficient implementations, is not a stable sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O (log n) additional space used by the stack during the recursion.

Class	Sorting algorithm
Worst case performance	O(n2)
Best case performance	O(n log n)
Average case performance	O(n log n)
Worst case space complexity	O(n) auxiliary (naive) O(log n) auxiliary (Sedgewick 1978)

Example

              

Algorithm

Partition(A; p; r)

1: x = A[r]

2: i   p 􀀀 1

3: for j   p to r 􀀀 1 do

4: if A[j] _ x then f

5: i   i+1

6: Exchange A[i] and A[j] g

7: Exchange A[i+1] and A[r]

8: return i+1

During