5 A list of 8 values is given below.
The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
- Carry out the first two passes of the sort.
A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
- State the maximum number of passes that could be required.
- Find the minimum number of passes that could be required.
The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is \(\mathrm { O } \left( n ^ { 2 } \right)\).
A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
- Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort.
A list of \(n\) values (where \(n > 10\) ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
- Explain why, in the best case, \(n - 3\) comparisons are used in the second pass.