Quick Sort
Method
- Choose the item at the median of the list to be the first pivot. (if no exact median, choose value to the right)
- Write down all the items that are less than the pivot, keepiung their order, in a sub list.
- Write down the pivot of the sub-list.
- Write down the remaining items (items greater than the pivot) in a sub list.
- Apply steps 1-4 to each sub list.
- When all items have been chosen as pivots, stop.
Example
18, 7, 14, 11, 9, 12, 21, 3, 10, 17 | 12 chosen as pivot
7, 11, 9, 3, 10, [12] 18, 14, 21, 17 | 9 and 21 chosen as pivot
7, 3, [9], 11, 10, [12], 18, 14, 17, [21] | 3, 10 and 14 chosen as pivot
[3], 7 [9], [10], 11, [12], [14], 18 17, [21] | 7, 11, 17 chosen as pivot
[3], [7], [9], [10], [11], [12], [14], [17], 18, [21] | 18 as pivot