7.03k Sorting: quick sort

1. $$\begin{array} { l l l l l l l l l l l } 4 & 6.5 & 7 & 1.3 & 2 & 5 & 1.5 & 6 & 4.5 & 6 & 1 \end{array}$$ The list of eleven numbers shown above is to be sorted into descending order.

1. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
2. Use the first-fit decreasing bin packing algorithm to pack the numbers into bins of size 10
3. Determine whether your answer to part (b) uses the minimum number of bins. You must justify your answer. A different list of eleven numbers is to be sorted into descending order using a bubble sort. The list after the second pass is
   1.6
   1.7
   1.5
   3.8
   3.3
   4.5
   4.8
   5.6
   5.4
   6.7
   9.1
4. Explain how you know that at least one of the first two passes of the bubble sort was not carried out correctly.

1. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker must be assigned to exactly one task and each task must be done by only one worker. The time, in hours, that each worker takes to complete each task is shown in the table below.

Reducing rows first, use the Hungarian algorithm to obtain an allocation which minimises the total time. You must explain your method and show the table after each stage.

1. Three workers, A, B and C, are each to be assigned to one of four tasks, P, Q, R and S.

Each worker must be assigned to at most one task, and each task must be done by at most one worker.
The amount, in pounds, that each worker will earn while assigned to each task is shown in the table below. The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the three workers.

1. Explain how the table should be modified.
   (2)
2. 1. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings.
   2. Explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage.
      

2. Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S. Each worker must be assigned to one task, and each task must be done by exactly one worker. Worker C cannot be assigned to task Q. The amount, in pounds, that each worker would earn when assigned to each task is shown in the table below. The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the four workers.

1. Explain how the table should be modified so that the Hungarian algorithm may be applied.
2. Modify the table so that the Hungarian algorithm may be applied.
3. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You should explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage.

1. Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.

Each task must be assigned to exactly one worker and each worker can do at most one task.
Worker B cannot be assigned to task R.
The amount, in pounds, that each worker will earn if they are assigned to each task is shown in the table below. The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the five workers.

1. Explain how the table should be modified to allow the Hungarian algorithm to be used, giving reasons for your answer.
2. Reducing rows first, use the Hungarian algorithm to obtain the maximum possible total earnings. You should explain how any initial row and column reductions were made and how you determined if the table was optimal at each stage.
   

1. Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S.

Each worker must be assigned to one task, and each task must be done by exactly one worker. Worker C cannot be assigned to task Q and worker D cannot be assigned to task S.
The time, in minutes, that each worker takes to complete each task is shown in the table below. The Hungarian algorithm is to be used to find the minimum total time for the four workers to complete the tasks.

1. Modify the table so that the Hungarian algorithm may be used.
2. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total time. You should explain how any initial row and column reductions are made and also how you determine if the table is optimal at each stage.
   

1. Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.

Each worker can only be assigned to at most one task, and each task must be done by at most one worker. Worker B cannot be assigned to task Q and worker E cannot be assigned to task S.
The time, in minutes, that each worker takes to complete each task is shown in the table below. The Hungarian algorithm is to be used to find the least total time to complete all four tasks.

1. Explain how the table should be modified so that the Hungarian algorithm can be applied.
2. 1. Use the Hungarian algorithm to obtain an allocation that minimises the total time.
   2. Explain how you determined if the table was optimal at each stage.
3. Calculate the least total time to complete all four tasks.
   

2. A team of 5 players, A, B, C, D and E, competes in a quiz. Each player must answer one of 5 rounds, \(\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }\) and T . Each player must be assigned to exactly one round, and each round must be answered by exactly one player. Player B cannot answer round Q, player D cannot answer round T, and player E cannot answer round R. The number of points that each player is expected to earn in each round is shown in the table. The team wants to maximise its total expected score.
The Hungarian algorithm is to be used to find the maximum total expected score that can be earned by the 5 players.

1. Explain how the table should be modified.
2. 1. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total expected score.
   2. Calculate the maximum total expected score.

1. Six workers, A, B, C, D, E and F, are to be assigned to five tasks, P, Q, R, S and T.

Each worker can be assigned to at most one task and each task must be done by just one worker. The time, in minutes, that each worker takes to complete each task is shown in the table below. Reducing rows first, use the Hungarian algorithm to obtain an allocation which minimises the total time. You must explain your method and show the table after each stage.

1. 0.2
1.7
1.9
1.2
1.4
1.5
2.1
3.0
3.2
3.3

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 of numbers is now to be sorted into descending order.
2. Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. For a list of \(n\) numbers, the quick sort algorithm has, on average, order \(n \log n\).
   Given that it takes 2.32 seconds to run the algorithm when \(n = 450\)
3. calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when \(n = 11250\). You should make your method and working clear.

3 A set of ten cards have the following values: \(\begin{array} { l l l l l l l l l l } 13 & 8 & 4 & 20 & 12 & 15 & 3 & 2 & 10 & 8 \end{array}\) Kerenza wonders if there is a set of these cards with a total of exactly 50 .

1. Which type of problem (existence, construction, enumeration or optimisation) is this? The five cards \(4,8,8,10\) and 20 have a total of 50.
2. How many ways are there to arrange three of these five cards (with the two 8 s being indistinguishable) so that the total of the numbers on the first two cards is less than the number on the third card?
3. How many ways are there to select (choose) three of the five cards so that the total of the numbers on the three cards is less than 25 ?
4. Show how quicksort works by using it to sort the original list of ten cards into increasing order.
   You should indicate the pivots used and which values are already known to be in their correct position.

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.

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.
      3. 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.
   4. Define the term 'matching'.
      (2)
   5. 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.
   6. 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.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. 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 .
   9. 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.

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.
      3. 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.
   4. Define the term 'matching'.
      (2)
   5. 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.
   6. 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.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. 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 .
   9. 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.
   10. 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.
   11. 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}$$
   12. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
   13. 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\).
   14. 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.
   15. Complete Diagram 1 in the answer book to show the early event times and late event times.
   16. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
   17. 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.
   18. 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)

4. Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan

1. Use the quick sort algorithm to sort the above list into alphabetical order.
   (5)
2. Use the binary search algorithm to locate the name Louis.

2 Use the quicksort algorithm to rearrange the following numbers into ascending order. Indicate clearly the pivots that you use. $$\begin{array} { l l l l l l l l } 18 & 23 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$

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.

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)

3 Four students, \(A , B , C\) and \(D\), are using different algorithms to sort 16 numbers into ascending order.

1. Student \(A\) uses the quicksort algorithm. State the number of comparisons on the first pass.
2. Student \(B\) uses the Shell sort algorithm. State the number of comparisons on the first pass.
3. Student \(C\) uses the shuttle sort algorithm. State the minimum number of comparisons on the final pass.
4. Student \(D\) uses the bubble sort algorithm. Find the maximum total number of comparisons.

12.1 \quad 9.3 \quad 15.7 \quad 10.9 \quad 17.4 \quad 6.4 \quad 20.1 \quad 7.9 \quad 8.1 \quad 14.0

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 \hfill [3]

The list is to be sorted into descending order.

1. 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.
   \hfill [4]
2. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear. \hfill [4]
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33 \hfill [3]
4. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer. \hfill [1]

\(650 \quad 431 \quad 245 \quad 643 \quad 455 \quad 134 \quad 710 \quad 234 \quad 162 \quad 452\)

1. The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. [5]

The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.

1. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.) [4]
2. Determine whether your solution to part (b) is optimal. Give a reason for your answer. [2]

The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper \((R)\), Palmer \((P)\), Boase \((B)\), Young \((Y)\), Thomas \((T)\), Kenney \((K)\), Morris \((M)\), Halliwell \((H)\), Wicker \((W)\), Garesalingam \((G)\).

1. Use the quick sort algorithm to sort the names above into alphabetical order. [5]
2. Use the binary search algorithm to locate the name Kenney. [4]

The table shows the marks obtained by students in a test. The students are listed in alphabetical order. Carry out a quick sort to produce a list of students in descending order of marks. You should show the result of each pass and identify your pivots clearly. (Total 5 marks)

Hajra	Vicky	Leisham	Alice	Nicky	June	Sharon	Tom	Paul
(H)	(V)	(L)	(A)	(N)	(J)	(S)	(T)	(P)

The table shows the names of nine people.

1. Use a quick sort to produce the list of names in ascending alphabetical order. You must make your pivots clear. [4]
2. Use the binary search algorithm on your list to locate the name Paul. [4]

(Total 8 marks)

A student is using a quicksort algorithm to rearrange a set of numbers into ascending order. She uses the first number in each list (or sublist) as the pivot. Her correct solution for the first three passes is as follows. Initial list: 10, 7, 4, 22, 13, 16, 19, 5 After 1st pass: 7, 4, 5, 10, 22, 13, 16, 19 After 2nd pass: 4, 5, 7, 10, 13, 16, 19, 22 After 3rd pass: 4, 5, 7, 10, 13, 16, 19, 22

1. State the pivots used for the 2nd pass. [2]
2. Write down the number of comparisons on each of the three passes. [3]
3. Explain whether the student has completed the algorithm. [1]