Exercises
Quicksort
- Assuming that the split function pivots around the first element
in the subarray,
- show the contents of subarray A after the call
split(A, first, last, splitPt); be sure to show the
location of index splitPt.
| 12 | 18 | 8 | 4 | 11 | 7 | 6 | 3 | 10 | 1 | 5 | 20 |
| [first] | | | | | | | | | | | [last] |
- How many times was the splitVal compared to an array element during
this call to
split(..) ?
- If all the elements in the subarray A are the same, state the
value of index splitPt after the first call to
split(A, first, last, splitPt)
- Briefly explain why the running time of function
split(..) is linear.
- How would you modify the quicksort function to sort
in descending order?
Continue to: Unit 3 / Prev / Next