7.03k Sorting: quick sort

1. \begin{displayquote} McCANN
SMITH
QUAGLIA
CONGDON
EVES
PATEL
BUSH
FOX
OSBORNE

1. Use a quick sort to produce a list of these names in alphabetical order. You must make your pivots clear.
2. Use the binary search algorithm on your list to locate the name PATEL. State the number of iterations you use. \end{displayquote} The binary search algorithm is to be used to search for a name in an alphabetical list of 641 names.
3. Find the maximum number of iterations needed, justifying your answer.

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{array} { l l l l l l l l l } 4.2 & 1.8 & 3.1 & 1.3 & 4.0 & 4.1 & 3.7 & 2.3 & 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 7.8
2. Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
3. The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-02_586_1356_906_358} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
4. Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. You must show clearly the order in which you consider the arcs. For each arc, state whether or not you are including it in your minimum spanning tree. A new spanning tree is required which includes the arcs AB and DE , and which has the lowest possible total weight.
5. Explain why Prim's algorithm could not be used to complete the tree.

1. $$\begin{array} { l l l l l l l l l l l } 2.5 & 0.9 & 3.1 & 1.4 & 1.5 & 2.0 & 1.9 & 1.2 & 0.3 & 0.4 & 3.9 \end{array}$$ The numbers in the list are the lengths, in metres, of eleven pieces of wood. They are to be cut from planks of wood of length 5 metres. You should ignore wastage due to cutting.

1. Calculate a lower bound for the number of planks needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to determine how these pieces could be cut from 5 metre planks.
3. Carry out a quick sort to produce a list of the lengths 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 to determine how these pieces could be cut from 5 metre planks.

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

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

1.

1. Use the first-fit bin packing algorithm to determine how the eleven numbers listed above can be packed into bins of size 14
2. The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
3. Apply the first-fit decreasing bin packing algorithm to the sorted list to pack the numbers into bins of size 14
4. Explain why the number of bins used in part (c) is optimal.
5. Use the binary search algorithm to try to locate 3.0 in the list of numbers. Clearly indicate how you choose your pivots and which part of the list is rejected at each stage.

20
23
17
15
22
19
25
13
28
32 A lower bound for the number of bins required is 4

1. Determine the range of possible values of \(n\). You must make your method clear.
   (3)
2. Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.
   (4) When the first-fit bin packing algorithm is applied to the original list of numbers, the following allocation is achieved. \end{table}
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-14_1193_1586_1270_185}
   Shortest path from A to J: \(\_\_\_\_\) Length of shortest path from A to J: \(\_\_\_\_\) \section*{2. \(\_\_\_\_\)} \section*{3.}

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   4. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-22_755_1157_246_404} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure}

   1. Activity	Immediately preceding activities
      A
      B
      C
      D
      E

      Activity	Immediately preceding activities
      F
      G
      H
      I
      J

      Activity	Immediately preceding activities
      K
      L
      M

      $$v = \ldots \quad x = \ldots \quad y = \ldots$$ \includegraphics[max width=\textwidth, alt={}, center]{d409aaae-811d-4eca-b118-efc927885f97-23_2255_56_315_37}
      \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-23_1153_1338_303_310}
      \section*{Grid 2} 5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-24_591_1433_255_260} \captionsetup{labelformat=empty} \caption{Figure 3
      [0pt] [The total weight of the network is 166]}
      \end{figure} 6.
      \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-26_1287_1645_301_162}
      \section*{Diagram 1} 7. \(\begin{array} { l l l l l l l l l l l } 14 & 20 & 23 & 17 & 15 & 22 & 19 & 25 & 13 & 28 & 32 \end{array}\)

1. 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.
2. Use the binary search algorithm on your list to locate the name Paul.

2.

1. \(\begin{array} { l l l l l l l l l l l } 18 & 20 & 11 & 7 & 17 & 15 & 14 & 21 & 23 & 16 & 9 \end{array}\) The list of numbers shown above is to be sorted into ascending order. Apply quick sort to obtain the sorted list. You must make your pivots clear. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-3_839_1275_614_395} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} Figure 3 represents a network of paths in a park. The number on each arc represents the length of the path in metres.
2. Using your answer to part (a) and Kruskal's algorithm, find a minimum spanning tree for the network in Figure 3. You should list the arcs in the order in which you consider them and state whether you are adding it to your minimum spanning tree.
3. Find the total weight of the minimum spanning tree.
   

1. Max Lauren John Hannah Kieran Tara Richard Imogen

1. Use a quick sort to produce a list of these names in ascending alphabetical order. You must make your pivots clear.
2. Use the binary search algorithm on your list from part (a) to try to locate the name 'Hugo'.

4. A builder is asked to replace the guttering on a house. The lengths needed, in metres, are $$0.6,4.0,2.5,3.2,0.5,2.6,0.4,0.3,4.0 \text { and } 1.0$$ Guttering is sold in 4 m lengths.

1. Carry out a quick sort to produce a list of the lengths needed in descending order. You should show the result of each pass and identify your pivots clearly.
2. Apply the first-fit decreasing bin-packing algorithm to your ordered list to determine the total number of 4 m lengths needed.
3. Does the answer to part (b) use the minimum number of 4 m lengths? You must justify your answer.

1. The table above shows the points obtained by each of the teams in a football league after they had each played 6 games. The teams are listed in alphabetical order. Carry out a quick sort to produce a list of teams in descending order of points obtained.

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.
0.6
0.2
0.4
0.5
0.7
0.1
0.9
0.3
1.5
1.6

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

1. $$\begin{array} { l l l l l l l l l } 31 & 10 & 38 & 45 & 19 & 47 & 35 & 28 & 12 \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. Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60
4. Determine whether the number of bins used in (c) is optimal. Give a reason for your answer.

6. \(\begin{array} { l l l l l l l l l } 24 & 14 & 8 & x & 19 & 25 & 6 & 17 & 9 \end{array}\) The numbers in the list represent the exact weights, in kilograms, of 9 suitcases. One suitcase is weighed inaccurately and the only information known about the unknown weight, \(x \mathrm {~kg}\), of this suitcase is that \(19 < x \leqslant 23\). The suitcases are to be transported in containers that can hold a maximum of 50 kilograms.

1. Use the first-fit bin packing algorithm, on the list provided, to allocate the suitcases to containers.
2. Using the list provided, carry out a quick sort to produce a list of the weights in descending order. Show the result of each pass and identify your pivots clearly.
3. Apply the first-fit decreasing bin packing algorithm to the ordered list to determine the 2 possible allocations of suitcases to containers. After the first-fit decreasing bin packing algorithm has been applied to the ordered list, one of the containers is full.
4. Calculate the possible integer values of \(x\). You must show your working.

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.

594518553471183171542

1. The list of numbers above is to be sorted into descending order. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper wire is sold in one metre lengths.
2. 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. Determine whether your solution to (b) is optimal. Give a reason for your answer.
   

3. \(\quad \begin{array} { l l l l l l l l l l } 42 & 21 & 15 & 16 & 35 & 10 & 31 & 11 & 27 & 39 \end{array}\)

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 65
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 65 The nine distinct numbers below are to be sorted into descending order $$\begin{array} { l l l l l l l l l } 23 & 14 & 17 & \boldsymbol { x } & 21 & 18 & 8 & 20 & 11 \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 first complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & \boldsymbol { x } & 21 & 18 & 14 & 20 & 11 & 8 \end{array}$$ After the second complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & 21 & 18 & \boldsymbol { x } & 20 & 14 & 11 & 8 \end{array}$$
4. Using this information, write down the smallest interval that must contain \(\boldsymbol { x }\). Give your answer as an inequality.

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.

4. $$\begin{array} { l l l l l l l l l l l } 25 & 9 & 32 & 16 & 17 & 23 & 18 & 12 & 4 & 8 & 40 \end{array}$$ The numbers in the list represent the weights, in kilograms, of eleven suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 50 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 suitcases to the containers.
3. Carry out a quick sort 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 to allocate the suitcases to the containers. The two heaviest suitcases are replaced with two suitcases both of which weigh \(x \mathrm {~kg}\). It is given that the lower bound for the number of containers needed is now one less than the number found in (a).
5. Determine the range of values for \(x\). You should make your working clear.

4. \(45 , \quad 56 , \quad 37 , \quad 79 , \quad 46 , \quad 18 , \quad 90 , \quad 81 , \quad 51\)

1. Using the quick sort algorithm, perform one complete iteration towards sorting these numbers into ascending order.
   (2)
2. Using the bubble sort algorithm, perform one complete pass towards sorting the original list into descending order. Another list of numbers, in ascending order, is $$7 , \quad 23 , \quad 31 , \quad 37 , \quad 41 , \quad 44 , \quad 50 , \quad 62 , \quad 71 , \quad 73 , \quad 94$$
3. Use the binary search algorithm to locate the number 73 in this list. \section*{5.} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-06_1246_1168_294_427}
   \end{figure} Figure 2 shows a network of roads connecting villages. The length of each road, in km, is shown. Village \(B\) has only a small footbridge over the river which runs through the village. It can be accessed by two roads, from \(A\) and \(D\). The driver of a snowplough, based at \(F\), is planning a route to enable her to clear all the roads of snow. The route should be of minimum length. Each road can be cleared by driving along it once. The snowplough cannot cross the footbridge. Showing all your working and using an appropriate algorithm,

1. 55534345928373452334247

The list of eleven numbers shown above is to be sorted into ascending order.

1. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly.
   (4) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c8134d3b-71cb-4b92-ac54-81a4ff8f3011-03_814_1545_614_260} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
2. Use Kruskal's algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree.
3. 1. Draw the minimum spanning tree on Diagram 1 in the answer book.
   2. State the total weight of the tree.
      

1. $$\begin{array} { l l l l l l l l l l l } 67 & 59 & 46 & 71 & 40 & 48 & 53 & 63 & 45 & 54 & 56 \end{array}$$ The list of eleven numbers shown above is to be sorted into descending order.
Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.