Partition: Tracing
- Explain and trace the quicksort algorithm on a particular data sequence.
Exercise Trace the first pass of running quicksort (applying partitioning process) on the following sequence. Take the right-most element as pivot.
$$ 20, \space 13, \space 7, \space 71, \space 31, \space 10, \space 5, \space 50, \space 17 $$
Solution
| 20 | 13 | 7 | 71 | 31 | 10 | 5 | 50 | 17 |
|---|---|---|---|---|---|---|---|---|
| 5 | 13 | 7 | 71 | 31 | 10 | 20 | 50 | 17 |
| 5 | 13 | 7 | 10 | 31 | 71 | 20 | 50 | 17 |
| 5 | 13 | 7 | 10 | 17 | 71 | 20 | 50 | 31 |
Items in bold indicate the elements which were swapped.