Give an example of a standard sorting algorithm that can be used when some of the values are not known until after the sorting has been started.
Becky needs to sort a list of numbers into increasing order.
She uses the following algorithm:
STEP 1: Let \(L\) be the first value in the input list.
Write this as the first value in the output list and delete it from the input list.
STEP 2: If the input list is empty go to STEP 7.
Otherwise let \(N\) be the new first value in the input list and delete this value from the input list.
STEP 3: \(\quad\) Compare \(N\) with \(L\).
STEP 4: If \(N\) is less than or equal to \(L\)
write the value of \(N\) immediately before \(L\) in the output list,
replace \(L\) with the first value in the new output list,
then go to STEP 2.
STEP 5: If \(N\) is greater than \(L\)
if \(L\) is the value of the last number in the output list, go to STEP 6;
otherwise, replace \(L\) with the next value in the output list and then go to STEP 3.
STEP 6: \(\quad\) Write the value of \(N\) immediately after \(L\) in the output list. Let \(L\) be the first value in the new output list and then go to STEP 2.
STEP 7: Print the output list and STOP.
Trace through Becky's algorithm when the input list is
$$\begin{array} { l l l l l l }
6 & 9 & 5 & 7 & 6 & 4
\end{array}$$
Complete the table in the Printed Answer Booklet, starting a new row each time that STEP 3 or STEP 7 is used.
You should not need all the lines in the Answer Booklet.
Becky measures the efficiency of her sort by counting using the number of times that STEP 3 is used.
How many times did Becky use STEP 3 in sorting the list from part (b)?
What is the greatest number of times that STEP 3 could be used in sorting a list of 6 values?
A computer takes 15 seconds to sort a list of 60 numbers using Becky's algorithm.
Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?