Quick Sort Execution

2

1. Use a quick sort to rearrange the following letters into alphabetical order. You must indicate the pivot that you use at each pass.
   P
   B
   M
   N
   J
   K
   R
   D
   (5 marks)
2. 1. Find the maximum number of swaps needed to rearrange a list of 8 numbers into ascending order when using a bubble sort.
      (1 mark)
   2. A list of 8 numbers was rearranged into ascending order using a bubble sort. The maximum number of swaps was needed. What can be deduced about the original list of numbers?
      (1 mark)

2

1. Use the quicksort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. You must indicate the pivot(s) being used on each pass. $$2 , \quad 12 , \quad 17 , \quad 18 , \quad 5 , \quad 13$$
2. For the first pass, write down the number of comparisons.

4 An algorithm must have an input, an output, be deterministic and finite.

1. Why is a counter sometimes used in an algorithm? A computer takes 0.2 seconds to sort a list of 500 numbers.
2. How long would you expect the computer to take to sort a list of 5000 numbers? Simon says that he can sort a list of numbers 'just by looking at them'.
3. Explain to Simon why sorting algorithms are needed.
4. Demonstrate how quick sort works by using it to sort the following list into increasing order. You should indicate the pivots used and which values are already known to be in their correct position. \(\begin{array} { l l l l l } 41 & 17 & 8 & 33 & 29 \end{array}\) For an average case the efficiency of quick sort is O (nlogn), where n is the number of items in the list.
5. Explain why quick sort is typically quicker than bubble sort and shuttle sort. When the number of comparisons made is used as a measure of the efficiency, the worst case for quick sort is no more efficient than the worst case for bubble sort. An arrangement of the five numbers from part (d) makes up a new list that is to be sorted using the bubble sort or the quick sort.
6. Without writing out all the passes, determine

5 A list of 8 values is given below. The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.

1. Carry out the first two passes of the sort. A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
2. 1. State the maximum number of passes that could be required.
   2. Find the minimum number of passes that could be required. The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is \(\mathrm { O } \left( n ^ { 2 } \right)\). A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
3. Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort. A list of \(n\) values (where \(n > 10\) ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
4. Explain why, in the best case, \(n - 3\) comparisons are used in the second pass.

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

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

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}

6. The twelve numbers in the list below are to be packed into bins of size \(n\), where \(n\) is a positive integer. When the first-fit bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 28315
Bin 2: 25161811
Bin 3: 352215
Bin 4: 2713

1. Based on the packing shown above, determine the possible values of \(n\). You must give reasons for your answer.
2. The original list of twelve 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. When the first-fit decreasing bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 35315
   Bin 2: 282716
   Bin 3: 252218
   Bin 4: 151311
3. Determine the value of \(n\). You must give a reason for your answer.

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.

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

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. (a) \(\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] \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.
(b) 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.
(c) 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.

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.

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.

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.