7.03k Sorting: quick sort

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.

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 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 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order. Shaun's list after the first pass through the sorting algorithm is given below. $$\begin{array} { l l l l l l l l l } 32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26 \end{array}$$

1. Explain how you know that Shaun did not use bubble sort. In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
2. Write down the two possibilities for the original list.
3. Write down the list after the second pass through the shuttle sort algorithm.
4. How many passes through shuttle sort were needed to sort the entire list? Shaun's sorted list is given below. $$\begin{array} { l l l l l l l l l } 15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53 \end{array}$$ Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
5. Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
6. Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .

3

1. Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l } 6 & 3 & 8 & 3 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
2. Shuttle sort is a quadratic order algorithm. Explain briefly what this statement means.

4. \begin{figure}[h] \end{figure} Figure 3 shows the graph \(K _ { 4 }\).

1. State the features of the graph that identify it as \(K _ { 4 }\).
2. In \(K _ { 4 }\), the Hamiltonian cycles \(A B C D A , B C D A B , C D A B C\) and \(D A B C D\) are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
   1. \(\quad K _ { 4 }\),
   2. \(K _ { 5 }\),
   3. \(K _ { 10 }\).
3. In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres: $$\begin{array} { l l l l l l l l } 27 & 25 & 29 & 32 & 19 & 24 & 17 & 26 \end{array}$$ Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.

2 The following table shows the times taken, in minutes, by five people, Ron, Sam, Tim, Vic and Zac, to carry out the tasks \(1,2,3\) and 4 . Sam takes \(x\) minutes, where \(8 \leqslant x \leqslant 12\), to do task 2. Each of the four tasks is to be given to a different one of the five people so that the total time for the four tasks is minimised.

1. Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
2. 1. Use the Hungarian algorithm, reducing columns first and then rows, to reduce the matrix to a form, in terms of \(x\), from which the optimum matching can be made.
   2. Hence find the possible way of allocating the four tasks so that the total time is minimised.
   3. Find the minimum total time.
3. After special training, Sam is able to complete task 2 in 7 minutes and is assigned to task 2. Determine the possible ways of allocating the other three tasks so that the total time is minimised.

2 A farmer has five fields. He intends to grow a different crop in each of four fields and to leave one of the fields unused. The farmer tests the soil in each field and calculates a score for growing each of the four crops. The scores are given in the table below. The farmer's aim is to maximise the total score for the four crops.

1. 1. Modify the table of values by first subtracting each value in the table above from 20 and then adding an extra row of equal values.
   2. Explain why the Hungarian algorithm can now be applied to the new table of values to maximise the total score for the four crops.
2. 1. By reducing rows first, show that the table from part (a)(i) becomes

      2	6	10	0	\(p\)
      0	5	12	4	8
      8	7	5	0	\(q\)
      1	8	2	4	0
      0	0	0	0	0

      State the values of the constants \(p\) and \(q\).
   2. Show that the zeros in the table from part (b)(i) can be covered by one horizontal and three vertical lines, and use the Hungarian algorithm to decide how the four crops should be allocated to the fields.
   3. Hence find the maximum possible total score for the four crops.

2 A team with five members is training to take part in a quiz. The team members, Abby, Bob, Cait, Drew and Ellie, attempted sample questions on each of the five topics and their scores are given in the table. For the actual quiz, each topic must be allocated to exactly one of the team members. The maximum total score for the sample questions is to be used to allocate the different topics to the team members.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(35 - x\).
2. Form a new table by subtracting each number in the table above from 35 . Hence show that, by reducing rows first then columns, the resulting table of values is as below, stating the values of the constants \(p\) and \(q\).

   8	6	8	0	4
   0	11	\(p\)	4	4
   10	4	6	0	12
   \(q\)	2	0	4	0
   0	0	6	6	0

3. Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. 1. Hence find the possible allocations of topics to the five team members so that the total score for the sample questions is maximised.
   2. State the value of this maximum total score.

3 Four pupils, Wendy, Xiong, Yasmin and Zaira, are each to be allocated a different memory coach from five available coaches: Asif, Bill, Connie, Deidre and Eric. Each pupil has an initial training session with each coach, and a test which scores their improvement in memory-recall produces the following results.

3

1. The list below is to be sorted into increasing order using bubble sort. \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
2. The list below is to be sorted into increasing order using shuttle sort. \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
3. Use the results from parts (a) and (b) to compare the efficiency of bubble sort with the efficiency of shuttle sort for the first three passes of this list. You do not need to consider what happens after these three passes.

3 The list of numbers below is to be sorted into increasing order. \(\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}\)

1. Sort the list using bubble sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
2. Now sort the original list using shuttle sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
3. Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list. Bubble sort and shuttle sort are both \(\mathrm { O } \left( n ^ { 2 } \right)\).
4. Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.

6 The following masses, in kg, are to be packed into bins. $$\begin{array} { l l l l l l l l l l } 8 & 5 & 9 & 7 & 7 & 9 & 1 & 3 & 3 & 8 \end{array}$$

1. Chloe says that first-fit decreasing gives a packing that requires 4 bins, but first-fit only requires 3 bins. Find the maximum capacity of the bins. First-fit requires one pass through the list and the time taken may be regarded as being proportional to the length of the list. Suppose that shuttle sort was used to sort the list into decreasing order.
2. What can be deduced, in this case, about the order of the time complexity, \(\mathrm { T } ( n )\), for first-fit decreasing?

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.

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

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.