Shuttle Sort Execution

2 A student is using a shuttle sort algorithm to rearrange a set of numbers into ascending order. Her correct solution for the first three passes is as follows.

1 Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l l } 6 & 5 & 9 & 4 & 5 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.

1

1. Use shuttle sort to put this list of values into decreasing order (from largest to smallest). $$\begin{array} { l l l l l l l l l } 18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22 \end{array}$$ Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.
2. The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.
3. Suppose that some stronger boxes are available, each of which can hold at most \(W \mathrm {~kg}\). Find the least value of \(W\) for which only four boxes are needed. Show a packing using four of these stronger boxes.

3

1. Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.
2. The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step. Step 1: Input the original list and call it list A.
   Step 2: Remove the first item in list \(A\) and call this item \(X\).
   Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.
   Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.
   Step 5: If there are still items in list A, repeat Step 4.
   Step 6: Count the number of items in list \(\mathbf { B }\) and call this \(\mathbf { N }\).
   Step 7: Put the items in list B at positions 1 to N of list A, item X at position \(\mathrm { N } + 1\) of list A and the items in list C at positions \(\mathrm { N } + 2\) onwards of list A.
   Step 8: Display list A.

3

1. Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l } 6 & 3 & 8 & 3 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
2. Shuttle sort is a quadratic order algorithm. Explain briefly what this statement means.

3

1. 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.
2. 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.
3. 1. How many times did Becky use STEP 3 in sorting the list from part (b)?
   2. 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.
4. Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?

1 Use a shuttle sort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. $$\begin{array} { l l l l l l l l } 23 & 3 & 17 & 4 & 6 & 19 & 14 & 3 \end{array}$$ (5 marks)

2

1. Use a shuttle sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 18 & 2 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$
2. State the number of comparisons and swaps (exchanges) for each of the first three passes.

2

1. Use a shuttle sort to rearrange into alphabetical order the following list of names:
   Rob, Eve, Meg, lan, Xavi
   Show the list at the end of each pass.
2. A list of ten numbers is sorted into ascending order, using a shuttle sort.
   1. How many passes are needed?
   2. Give the maximum number of comparisons needed in the sixth pass.
   3. Given that the list is initially in descending order, find the total number of swaps needed.
      [0pt] [4 marks]

Tom has some packages that he needs to sort into order of decreasing weight. The weights, in kg, given on the packages are as follows. 3 \quad 6 \quad 2 \quad 6 \quad 5 \quad 7 \quad 1 \quad 4 \quad 9 Use shuttle sort to put the weights into decreasing order (from largest to smallest). Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass. Write down the total number of passes, the total number of comparisons and the total number of swaps used. [6]