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}