Definition:
Quick Sort is an algorithm that sorts unsorted lists and arrays.
In worst case, time complexity of Quick Sort is O ( n^2). In average and best case, time complexity of that algorithm is O (n logn).
It is divide and conquer algorithm and invented by Tony Hoare.
It is also in-place algorithm, so it doesn’t require extra space of memory. This property make this algorithm more popular in practice.
Properties of Quick Sort:
- Not Stable,
- Not Adaptive,
- O ( logn) extra space,
- Often faster algorithm than other O ( n logn) algoirthms in practice.
- In-place algorithm.
How does it work?
1. Pick an element from array. This element is called Pivot.
2. Reorder the array according to pivot. Elements smaller than pivot come before pivot and elements bigger than pivot come after the pivot. This operation is called partition. Pivot gets its final position after partitioning.
3. Recursively do it again for subarrays of the list.
In the figure below, you can see the animated figure of this algorithm.
Animated Figure of Quick Sort
In the example below, you can see pivot (4), partition algorithm and partioning in sub arrays.
Quick Sort
Animation:
For better understanding, go to this animation page.
Pseudocode:
QuickSort: quicksort(A, i, k): if i < k: p := partition(A, i, k) quicksort(A, i, p - 1) quicksort(A, p + 1, k) Partition: // left is the index of the leftmost element of the subarray // right is the index of the rightmost element of the subarray (inclusive) // number of elements in subarray = right-left+1 partition(array, left, right) pivotIndex := choose-pivot(array, left, right) pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] storeIndex := left for i from left to right - 1 if array[i] ≤ pivotValue swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // Move pivot to its final place return storeIndex
References:
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (second ed.), MIT Press and McGraw-Hill,
Figures from: http://en.wikipedia.org