7.03j Sorting: bubble sort and shuttle sort

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}

3. $$\begin{array} { l l l l l l l l l l } 1.1 & 0.7 & 1.9 & 0.9 & 2.1 & 0.2 & 2.3 & 0.4 & 0.5 & 1.7 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 3 The list is to be sorted into descending order.
2. 1. Starting at the left-hand end of the list, perform one pass through the list using a bubble sort. Write down the list that results at the end of your first pass.
   2. Write down the number of comparisons and the number of swaps performed during your first pass. After a second pass using this bubble sort, the updated list is $$\begin{array} { l l l l l l l l l l } 1.9 & 1.1 & 2.1 & 0.9 & 2.3 & 0.7 & 0.5 & 1.7 & 0.4 & 0.2 \end{array}$$
3. Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
4. Apply the first-fit decreasing bin packing algorithm to your fully sorted list to pack the numbers into bins of size 3

3.
6.4
7.9
8.1
12.19 .3
14.0
15.7
17.4
20.1

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 The list is to be sorted into descending order.
2. 1. Starting at the left-hand end of the list, perform two passes through the list using a bubble sort. Write down the state of the list that results at the end of each pass.
   2. Write down the total number of comparisons and the total number of swaps performed during your two passes.
3. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear.
4. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33
5. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer.

4. \(\begin{array} { l l l l l l l l l } 23 & 18 & 27 & 9 & 25 & 10 & 12 & 30 & 24 \end{array}\) The numbers in the list represent the weights, in kilograms, of nine suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 45 kilograms.

1. Calculate a lower bound for the number of containers that will be needed to transport the suitcases.
2. Use the first-fit bin packing algorithm to allocate the suitcases to the containers.
3. Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each complete pass.
4. Use the first-fit decreasing bin packing algorithm to allocate the suitcases to the containers.
5. Explain why it is not possible to transport the suitcases using fewer containers than the number used in (d).

6. $$\begin{array} { l l l l l l l l l l } 30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43 \end{array}$$ The numbers in the list above represent the lengths, in cm, of some pieces of electrical wire. The wire is sold in one metre lengths.

1. Use the first-fit bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting. The list of numbers above is to be sorted into ascending order.
   Starting at the left-hand end of the list, after three passes of the bubble sort, the list is $$\begin{array} { l l l l l l l l l l } 11 & 21 & 30 & 16 & 4 & 39 & 43 & 50 & 53 & 60 \end{array}$$
2. 1. Write down the list that results at the end of the fourth pass.
   2. Write down the number of comparisons and swaps performed during the fourth pass. The original list of numbers is now to be sorted into descending order.
3. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.

4. $$\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}$$ The numbers in the list above represent the weights, in kilograms, of 11 boxes. John must transport all the boxes using his van. You may assume the van has sufficient space for any combination of boxes. Each van load of boxes must weigh at most 475 kg .

1. Calculate a lower bound for the number of van loads needed to transport all 11 boxes.
2. Use the first-fit bin packing algorithm to show how the boxes could be put into van loads. State the number of van loads needed according to this solution.
3. Carry out a quick sort on the numbers in the list given above to produce a list of the weights in descending order. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm on your ordered list to show how the boxes could be put into van loads. State the number of van loads needed according to this solution. Due to volume restrictions, the van cannot transport more than three boxes at any one time.
5. Show how the boxes could now be put into the minimum number of van loads.

4. $$\begin{array} { l l l l l l l l l l } 35 & 17 & 10 & 7 & 28 & 23 & 41 & 15 & 20 & 29 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 60
2. The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
3. Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 60 The ten distinct numbers below are to be sorted into descending order. $$\begin{array} { l l l l l l l l l l } 20 & 24 & 17 & 26 & 8 & 15 & x & y & 19 & 12 \end{array}$$ A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list.
   After the second complete pass the list is $$\begin{array} { l l l l l l l l l l } 24 & 26 & 20 & 17 & 15 & y & 19 & 12 & x & 8 \end{array}$$
4. Find the constraints on the values of \(x\) and \(y\).

3. \(\quad \begin{array} { l l l l l l l l l l } 2.6 & 0.8 & 2.1 & 1.2 & 0.9 & 1.7 & 2.3 & 0.3 & 1.8 & 2.7 \end{array}\)

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 The list is to be sorted into descending order.
2. 1. Starting at the left-hand end of the above list, perform two passes through the list using a bubble sort. Write down the lists that result at the end of the first pass and the second pass.
   2. Write down, in the table in the answer book, the number of comparisons and the number of swaps performed during each of these two passes. After a third pass using this bubble sort, the updated list is $$\begin{array} { l l l l l l l l l l } 2.6 & 2.1 & 1.7 & 2.3 & 1.2 & 1.8 & 2.7 & 0.9 & 0.8 & 0.3 \end{array}$$
3. Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
4. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 5

1. \(\begin{array} { l l l l l l l l l l } 17 & 9 & 15 & 8 & 20 & 13 & 28 & 4 & 12 & 5 \end{array}\) \section*{Question 1 continued} \section*{Question 1 continued} \section*{Question 1 continued}

2. A list of \(n\) numbers needs to be sorted into descending order starting at the left-hand end of the list.

1. Describe how to carry out the first pass of a bubble sort on the numbers in the list.
2. 1. State which number in the list is guaranteed to be in the correct final position after the first pass.
   2. Write down the maximum number of passes required to sort a list of \(n\) numbers.
3. The numbers below are to be sorted into descending order. Use a bubble sort, starting at the left-hand end of the list, to obtain the sorted list. You need only give the state of the list after each pass. $$\begin{array} { l l l l l l l l l } 11 & 9 & 4 & 13 & 5 & 1 & 7 & 12 & 8 \end{array}$$
4. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 21

1. $$\begin{aligned} & \text { Kerry (K) } \\ & \text { Nikki (N) } \\ & \text { Violet (V) } \\ & \text { Dev (D) } \\ & \text { Henri (H) } \\ & \text { Leslie (L) } \\ & \text { Enlai (E) } \\ & \text { Sylvester (S) } \\ & \text { Joan (J) } \end{aligned}$$ A binary search is to be performed on the names in the list above to locate the name Leslie.

1. Explain why a binary search cannot be performed with the list in its present form.
2. Using an appropriate algorithm, alter the list so that a binary search can be performed. You should state the name of the algorithm you use and show the list after each complete iteration.
3. Use the binary search algorithm to locate the name Leslie in the altered list you obtained in (b). You must make your method clear. The binary search algorithm is to be used to search for a name in an alphabetical list of 727 names.
4. Find the maximum number of iterations needed. You should justify your answer.

3. Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below. $$\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}$$

1. Calculate a lower bound for the number of tour groups required. You must make your method clear.
2. Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups. The above list of numbers is to be sorted into descending order.
3. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
4. Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-04_712_1141_1363_463} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} [The total weight of the network is 227.2]
   Figure 2 represents the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum's entrance at A .
5. Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.
6. Write down a possible shortest route, giving its length. Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.
7. State the finishing vertex of Sally's new route and calculate the difference in length between this new route and the route found in (f).

6. 2. \begin{figure}[h] \end{figure} Shortest route: \(\_\_\_\_\) Length of shortest route: \(\_\_\_\_\) \begin{figure}[h] \end{figure} 3. \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\) \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\) \begin{figure}[h] \end{figure} 4. \includegraphics[max width=\textwidth, alt={}, center]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-20_572_1454_1021_248} \section*{Key:} \section*{Diagram 1} 5. \section*{Diagram 1} 6.

2.

1. 1. Describe how to carry out the first pass of a bubble sort when it is used to sort a list of \(n\) numbers into ascending order.
   2. Write down the circumstances under which a bubble sort stops. A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads
      0.9
      0.5
      0.7
      1.2
      1.5
      1.4
      1.1
      1.7
      2.2
      3.2
2. Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.
3. Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.
4. Use the first-fit decreasing bin packing algorithm to determine how the ten numbers listed above can be packed into bins of size 4
   

1. \(\begin{array} { l l l l l l l l l l l l l } 16 & 23 & 18 & 9 & 4 & 20 & 35 & 5 & 17 & 13 & 6 & 11 \end{array}\) The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels are to be transported in containers that will each hold a maximum weight of 45 kg .

1. Calculate a lower bound for the number of containers needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to allocate the parcels to the containers.
3. Carry out a bubble sort, starting at the left-hand end of the list, to produce a list of the weights in descending order. You should only give the state of the list after each pass.
4. Use the first-fit decreasing bin packing algorithm to allocate the parcels to the containers.

1. \(\quad \begin{array} { l l l l l l l l l l } 175 & 135 & 210 & 105 & 100 & 150 & 60 & 20 & 70 & 125 \end{array}\)

The numbers in the list above represent the weights, in kilograms, of ten crates. The crates are to be transported in trucks that can each hold a maximum total crate weight of 300 kg .

1. Calculate a lower bound for the number of trucks that will be needed to transport the crates.
2. Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each pass.
3. Use the first-fit decreasing bin packing algorithm to allocate the crates to the trucks.
   

2. A list of eleven numbers is to be sorted into descending order. After one pass, the quick sort algorithm produces the following list $$\begin{array} { l l l l l l l l l l l } 17 & 33 & 14 & 25 & 23 & 28 & 21 & 13 & 9 & 6 & 10 \end{array}$$

1. State, with a reason, which number was used as a pivot for the first pass.
2. Starting at the left-hand end of the above list, obtain the fully sorted list using a bubble sort. You need to write down only the list that results at the end of each pass.
3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 85

2. $$\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}$$ The numbers represent the sizes, in megabytes (MB), of eight files.
The files are to be stored on 50 MB discs.

1. Calculate a lower bound for the number of discs needed to store all eight files.
2. Use the first-fit bin packing algorithm to fit the files onto the discs.
3. Perform a bubble sort on the numbers in the list to sort them into descending order. You need only write down the final result of each pass.
4. Use the first-fit decreasing bin packing algorithm to fit the files onto the discs.

5.

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 20.
2. The list of numbers is to be sorted into descending order. Use a bubble sort to obtain the sorted list, giving the state of the list after each complete pass.
3. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 20.
4. Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.

5. $$90,50,55,40,20,35,30,25,45$$

1. Use the bubble sort algorithm to sort the list of numbers above into descending order showing the rearranged order after each pass. Jessica wants to record a number of television programmes onto video tapes. Each tape is 2 hours long. The lengths, in minutes, of the programmes she wishes to record are: $$\text { 55, 45, 20, 30, 30, 40, 20, 90, 25, 50, } 35 \text { and } 35 .$$
2. Find the total length of programmes to be recorded and hence determine a lower bound for the number of tapes required.
3. Use the first fit decreasing algorithm to fit the programmes onto her 2-hour tapes. Jessica's friend Amy says she can fit all the programmes onto 4 tapes.
4. Show how this is possible.

1. A carpet fitter needs the following lengths, in metres, of carpet.

$$\begin{array} { l l l l l l l l l } 20 & 33 & 19 & 24 & 31 & 22 & 27 & 18 & 25 \end{array}$$ He cuts them from rolls of length 50 m .

1. Calculate a lower bound for the number of rolls he needs. You must make your method clear.
2. Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m .
3. Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.
4. Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.
   

4.

1. Sam (S)
2. Janelle (J)
3. Haoyu (H)
4. Alfie (A)
5. Cyrus (C)
6. Komal (K)
7. Polly (P)
8. David (D)
9. Tom (T)
10. Lydia (L)

A binary search is to be performed on the names in the list above to locate the name Lydia.

1. Using an appropriate algorithm, rearrange the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
2. Use the binary search algorithm to locate the name Lydia in the list you obtained in (a). You must make your method clear.
   

2. $$\begin{array} { l l l l l l l l l l } 18 & 29 & 48 & 9 & 42 & 31 & 37 & 24 & 27 & 41 \end{array}$$ The numbers above are Alan's batting scores for the first 10 cricket matches of the season.

1. Use a quick sort to sort this list of numbers into ascending order. You must make your pivots clear. Alan's batting scores for the final 10 cricket matches of the same season were \(\begin{array} { l l l l l l l l l l } 72 & 53 & 89 & 91 & 68 & 67 & 90 & 77 & 83 & 75 \end{array}\)
2. Carry out a bubble sort on this second list of numbers to produce a list of these scores in ascending order. You need only give the state of the list after each pass. Alan's combined batting scores for the entire season were $$\begin{array} { l l l l l l l l l l l l l l l l l l l l } 9 & 18 & 24 & 27 & 29 & 31 & 37 & 41 & 42 & 48 & 53 & 67 & 68 & 72 & 75 & 77 & 83 & 89 & 90 & 91 \end{array}$$
3. Use the binary search algorithm to locate 68 in the combined list of 20 scores. You must make your method clear.

2. A list of nine numbers needs to be sorted into descending order.

1. Describe how to carry out the first pass of a bubble sort on the numbers in the list. Mayleen used a sorting algorithm to sort a list of nine numbers into descending order. Mayleen's list after the first pass through the algorithm is given below. $$\begin{array} { l l l l l l l l l } 30 & 33 & 35 & 27 & 20 & 24 & 21 & 15 & 19 \end{array}$$
2. Explain how you know that Mayleen did not use the bubble sort algorithm. Given that Mayleen used the quick sort algorithm,
3. write down the number that was used as a pivot for the first pass,
4. complete the quick sort to obtain a fully sorted list in descending order. You must make your pivots clear.
5. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60 A tenth number, 18, is added to the list of nine numbers.
6. Determine whether it is possible to pack the ten numbers into 4 bins of size 60 . You must justify your answer.

6. \(\begin{array} { l l l l l l l l l l } 55 & 80 & 25 & 84 & 25 & 34 & 17 & 75 & 3 & 5 \end{array}\)

1. The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each complete pass. The numbers in the list represent weights, in grams, of objects which are to be packed into bins that hold up to 100 g .
2. Determine the least number of bins needed.
3. Use the first-fit decreasing algorithm to fit the objects into bins which hold up to 100 g .