Comparing Sorting Algorithms

1 Owen and Hari each want to sort the following list of marks into decreasing order. $$\begin{array} { l l l l l l l l l l } 31 & 28 & 75 & 87 & 42 & 43 & 70 & 56 & 61 & 95 \end{array}$$

1. Owen uses bubble sort, starting from the left-hand end of the list.
   1. Show the result of the first pass through the list. Record the number of comparisons and the number of swaps used in this first pass. Which marks, if any, are guaranteed to be in their correct final positions after the first pass?
   2. Write down the list at the end of the second pass of bubble sort.
   3. How many more passes are needed to get the value 95 to the start of the list?
   4. Hari uses shuttle sort, starting from the left-hand end of the list. Show the results of the first and the second pass through the list. Record the number of comparisons and the number of swaps used in each of these passes.
   5. Explain why, for this particular list, the total number of comparisons will be greater using bubble sort than using shuttle sort. Shuttle sort is a quadratic order algorithm.
   6. If it takes Hari 20 seconds to sort a list of ten marks using shuttle sort, approximately how long will it take Hari to sort a list of fifty marks?

2 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order. Shaun's list after the first pass through the sorting algorithm is given below. $$\begin{array} { l l l l l l l l l } 32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26 \end{array}$$

1. Explain how you know that Shaun did not use bubble sort. In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
2. Write down the two possibilities for the original list.
3. Write down the list after the second pass through the shuttle sort algorithm.
4. How many passes through shuttle sort were needed to sort the entire list? Shaun's sorted list is given below. $$\begin{array} { l l l l l l l l l } 15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53 \end{array}$$ Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
5. Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
6. Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .

3

1. The list below is to be sorted into increasing order using bubble sort. \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
2. The list below is to be sorted into increasing order using shuttle sort. \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
3. Use the results from parts (a) and (b) to compare the efficiency of bubble sort with the efficiency of shuttle sort for the first three passes of this list. You do not need to consider what happens after these three passes.

3 The list of numbers below is to be sorted into increasing order. \(\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}\)

1. Sort the list using bubble sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
2. Now sort the original list using shuttle sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
3. Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list. Bubble sort and shuttle sort are both \(\mathrm { O } \left( n ^ { 2 } \right)\).
4. Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.

7 A network is formed by weighting the graph below using the listed arc weights. \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-8_168_190_310_258} \(\begin{array} { l l l l l l l l } 2.9 & 0.9 & 1.5 & 3.5 & 4.2 & 5.3 & 4.7 & 2.3 \end{array}\)

1. 1. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using bubble sort.
   2. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using shuttle sort. In the remaining passes of bubble sort another 14 comparisons are made.
      In the remaining passes of shuttle sort another 11 comparisons are made.
      The total number of swaps needed is the same for both sorting methods.
2. Use the total number of comparisons and the total number of swaps to compare the efficiency of bubble sort and shuttle sort for sorting this list of weights. The sorted list of arc weights for the network is as follows. \(\begin{array} { l l l l l l l l } 0.9 & 1.5 & 2.3 & 2.9 & 3.5 & 4.2 & 4.7 & 5.3 \end{array}\) These weights can be given to the arcs of the graph in several ways to form different networks.
3. 1. What is the smallest weight that does not have to appear in a minimum spanning tree for any of these networks? You must explain your reasoning.
   2. Show a way of weighting the arcs, using the weights in the list, that results in the largest possible total for a minimum spanning tree. You should state the total weight of your minimum spanning tree.
   3. Determine the total weight of an optimal solution of the route inspection problem for the network found in part (c)(ii). \section*{END OF QUESTION PAPER}

7 The numbers 17, 3, 16 and 4 are to be sorted into ascending order.
The following four methods are to be compared: bubble sort, shuttle sort, Shell sort and quick sort (with the first number used as the pivot). A student uses each of the four methods and produces the correct solutions below. Each solution shows the order of the numbers after each pass.

1. Write down which of the four solutions is the bubble sort, the shuttle sort, the Shell sort and the quick sort.
2. For each of the four solutions, write down the number of comparisons and swaps (exchanges) on the first pass.