4 An algorithm must have an input, an output, be deterministic and finite.
- Why is a counter sometimes used in an algorithm?
A computer takes 0.2 seconds to sort a list of 500 numbers.
- How long would you expect the computer to take to sort a list of 5000 numbers?
Simon says that he can sort a list of numbers 'just by looking at them'.
- Explain to Simon why sorting algorithms are needed.
- Demonstrate how quick sort works by using it to sort the following list into increasing order. You should indicate the pivots used and which values are already known to be in their correct position.
\(\begin{array} { l l l l l } 41 & 17 & 8 & 33 & 29 \end{array}\)
For an average case the efficiency of quick sort is O (nlogn), where n is the number of items in the list. - Explain why quick sort is typically quicker than bubble sort and shuttle sort.
When the number of comparisons made is used as a measure of the efficiency, the worst case for quick sort is no more efficient than the worst case for bubble sort.
An arrangement of the five numbers from part (d) makes up a new list that is to be sorted using the bubble sort or the quick sort.
- Without writing out all the passes, determine
- the worst case list
- the total number of comparisons for the worst case list
for each of the algorithms in turn.