Bubble Sort Execution

2

1. Use a bubble 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 } 19 & 3 & 7 & 20 & 2 & 6 & 5 & 15 \end{array}$$
2. Write down the number of comparisons and the number of swaps during the first pass.
   (2 marks)

7 Mr Rank and Miss File need to sort a pile of examination scripts into increasing order of mark. Mr Rank first goes through the pile of scripts and puts each script into one of two piles, depending on whether the mark is below 50 or not. He then sorts the scripts in the 'below 50 ' pile and Miss File sorts the scripts in the '50 and above' pile. At the end they put the two sorted piles together again.

1. The scripts in the 'below 50' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 34 & 42 & 27 & 31 & 12 & 48 & 24 & 37 \end{array}$$ Use bubble sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. Give the number of swaps and the number of comparisons that were used in sorting this list.
2. The scripts in the '50 and above' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 95 & 74 & 61 & 87 & 71 & 82 & 53 & 57 \end{array}$$ Use shuttle sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. List the number of swaps and number of comparisons that were used in sorting this list.
3. Explain why splitting the original list into two piles is a linear order algorithm.
4. Both bubble sort and shuttle sort are quadratic order algorithms. Mr Rank and Miss File use their method to sort a pile of 100 scripts. It takes about 50 seconds to split the pile and about 250 seconds to do each sort. As the sorts are done at the same time, this gives a total time taken of about 300 seconds, or 6 minutes. Approximately how long would Mr Rank and Miss File take to split a pile of 500 scripts into two roughly equal piles and sort the piles? Show all your working.
   [0pt] [4]

1 The list below is to be sorted into increasing order using bubble sort, starting at the left-hand end of the list. $$\begin{array} { l l l l l l } 24 & 57 & 9 & 31 & 16 & 4 \end{array}$$

1. Show which values are compared and which are swapped in the first pass. Write down the list that results at the end of the first pass.
2. Without showing the individual comparisons and swaps, write down the lists that result after the second pass and after the third pass.
3. In total there will be five passes made in carrying out bubble sort on the list. Write down how many swaps are made in each pass.

1 The following list is to be sorted into increasing order, from smallest to largest. $$\begin{array} { l l l l l l } 15 & 7 & 9 & 26 & 10 & 4 \end{array}$$ Bubble sort is to be used, starting at the left-hand end of the list, so that after the completion of the first pass the largest value will be at the right-hand end of the list.

1. Write down the list that results at the end of the first pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
2. After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 4 & 10 & 15 & 26 \end{array}$$ Write down the list that results at the end of the fourth pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
3. How many comparisons are needed in total to sort the list using bubble sort? Shuttle sort is then used to sort the original list, into increasing order, starting at the left-hand end of the list.
4. Write down the list that results at the end of the first pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
5. After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 15 & 26 & 10 & 4 \end{array}$$ Write down the list that results at the end of the fourth pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
6. How many comparisons and how many swaps are made in the fifth pass? In sorting the original list, both methods use a total of 9 swaps.
7. Which of the two methods is the more efficient at sorting this list? Support your answer with a reason.

2. (a) The following list of numbers is to be sorted into descending order. $$\begin{array} { l l l l l l } 35 & 23 & 10 & 46 & 24 & 11 \end{array}$$ Use the Bubble sort algorithm to obtain a sorted list, giving the state of the list at each stage where two values could be interchanged.
(b) Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
(c) Use the first-fit decreasing algorithm to fit the data in part (a) into bins of size 50. Explain how you decided in which bin to place the number 11.

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.

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 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.

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.

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 .

6 This list is to be sorted into decreasing order, ending up with 31 in the first position and 4 in the last position.
15
4
12
23
14
16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12

1. 11
17
10
14
8
13
6
4
15
7

1. Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
2. Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
3. Calculate a lower bound for the minimum number of bins required. You must show your working.

17
10
14
8
13
6
4
15
7

1. Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
2. Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
3. Calculate a lower bound for the minimum number of bins required. You must show your working.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
   1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
   2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
   3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
      2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
   4. State the new minimum cost of connecting the nine buildings.
      3. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
   5. Define the term 'matching'.
      (2)
   6. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
      (3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
   7. Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
      (3)
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
      [0pt] [The total weight of the network is 367 metres]}
      \end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
      The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
   8. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   9. Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
   10. Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.
       5. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-6_560_1134_251_470} \captionsetup{labelformat=empty} \caption{Figure 5}
       \end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road.
   11. Use Dijkstra's algorithm to find the shortest route from S to T . State your route and its length. The road represented by arc CE is now closed for repairs.
   12. Find two shortest routes from S to T that do not include arc CE . State the length of these routes.
       (3)
       6. A linear programming problem in \(x\) and \(y\) is described as follows. Minimise \(\quad C = 2 x + 5 y\) subject to $$\begin{aligned} x + y & \geqslant 500 \\ 5 x + 4 y & \geqslant 4000 \\ y & \leqslant 2 x \\ y & \geqslant x - 250 \\ x , y & \geqslant 0 \end{aligned}$$
   13. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
   14. Use point testing to determine the exact coordinates of the optimal point, P. You must show your working. The first constraint is changed to \(x + y \geqslant k\) for some value of \(k\).
   15. Determine the greatest value of \(k\) for which P is still the optimal point.
       7. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-8_582_1226_248_422} \captionsetup{labelformat=empty} \caption{Figure 6}
       \end{figure} A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   16. Complete Diagram 1 in the answer book to show the early event times and late event times.
   17. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
   18. Use your cascade chart to determine a lower bound for the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. The project is to be completed in the minimum time using as few workers as possible.
   19. Schedule the activities, using Grid 2 in the answer book.
       8. A charity produces mixed packs of posters and flyers to send out to sponsors. Pack A contains 40 posters and 20 flyers.
       Pack B contains 30 posters and 50 flyers.
       The charity must send out at least 15000 flyers.
       The charity wants between \(40 \%\) and \(60 \%\) of the total packs produced to be Pack As.
       Posters cost 15p each and flyers cost 3p each.
       The charity wishes to minimise its costs.
       Let \(x\) represent the number of Pack As produced, and \(y\) represent the number of Pack Bs produced.
       Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.
       You should not attempt to solve the problem.
       (Total 6 marks)

2

1. Use a bubble sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 13 & 16 & 10 & 11 & 4 & 12 & 6 & 7 \end{array}$$
2. State the number of comparisons and the number of swaps (exchanges) for each of the first three passes.

25 22 30 18 29 21 27 21 The list of numbers above is to be sorted into descending order.

1. 1. Perform the first pass of a bubble sort, giving the state of the list after each exchange.
   2. Perform further passes, giving the state of the list after each pass, until the algorithm terminates.
   [5]

The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm.

1. 1. Show the result of applying the first fit decreasing bin packing algorithm to this situation.
   2. Determine whether your solution to \((b)\) \((i)\) has used the minimum number of 50 cm rods.
   [4]

52 48 50 45 64 47 53 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 completed pass. [4]