Sorting Algorithms

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}

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.

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.

1 \includegraphics[max width=\textwidth, alt={}, center]{a7bca340-6947-42b5-bc35-e6d429d6bed7-2_953_559_347_753}

1. Trace through the flowchart above using the input \(N = 97531\). You only need to record values when they change.
2. Explain why the process in the flowchart is finite.

1 A student is using the algorithm below. Trace the algorithm in the case where \(A = 5\) and \(B = 3\).

3. \begin{figure}[h] \end{figure} An algorithm for finding the positive real root of the equation \(8 x ^ { 4 } + 5 x - 12 = 0\) is described by the flow chart shown in Figure 2.

1. Use the flow chart, with \(a = 1\), to complete the table in the answer book, stating values to at least 6 decimal places. Give the final output correct to 5 decimal places. Given that the value of the input \(a\) is a non-negative real number,
2. determine the set of values for \(a\) that cannot be used to find the positive real root of \(8 x ^ { 4 } + 5 x - 12 = 0\) using this flow chart.

52 48 50 45 64 47 53 The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each completed pass. [4]

2

1. Use a bubble sort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. $$\begin{array} { l l l l l l l l } 19 & 3 & 7 & 20 & 2 & 6 & 5 & 15 \end{array}$$
2. Write down the number of comparisons and the number of swaps during the first pass.
   (2 marks)

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

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

10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

1

1. Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each. $$\begin{array} { l l l l l l l } 2 & 4 & 3 & 3 & 2 & 5 & 4 \end{array}$$ Show clearly which weights are packed into which boxes.
2. Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.
3. First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?

1 Some jars need to be packed into small crates.
There are 17 small jars, 7 medium jars and 3 large jars to be packed.

• A medium jar takes up the same space as four small jars.
• A large jar takes up the same space as nine small jars.

Each crate can hold:

• at most 12 small jars,
• or at most 3 medium jars,
• or at most 1 large jar (and 3 small jars),
• or a mixture of jars of different sizes.
  1. One strategy is to fill as many crates as possible with small jars first, then continue using the medium jars and finally the large jars.

Show that this method will use seven crates. The jars can be packed using fewer than seven crates.

The jars are to be packed in the minimum number of crates possible.

• Describe how the jars can be packed in the minimum number of crates.
• Explain how you know that this is the minimum number of crates.

Some other numbers of the small, medium and large jars need to be packed into boxes.
The number of jars that a box can hold is the same as for a crate, except that

• a box cannot hold 3 medium jars.
• Describe a packing strategy that will minimise the number of boxes needed.

1. Use the binary search algorithm to try to locate the name Hilbert in the following alphabetical list. Clearly indicate how you chose your pivots and which part of the list is being rejected at each stage.

1. (a) Use the binary search algorithm to locate the name PENICUIK in the following list.

\begin{displayquote} ANKERDINE CULROSS DUNOON ELGIN FORFAR FORT WILLIAM HADDINGTON KINCARDINE LARGS MALLAIG MONTROSE PENICUIK ST. ANDREWS THURSO
(b) Use the same algorithm to attempt to locate PENDINE.
(c) Explain the purpose of the mid-point in dividing up the ordered list when using this algorithm. \end{displayquote}

2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.

1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
2. A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.

2 A student is using a shuttle sort algorithm to rearrange a set of numbers into ascending order. Her correct solution for the first three passes is as follows.

2 A student is using a shuttle sort algorithm to rearrange a set of numbers into ascending order. Her correct solution for the first three passes is as follows.

3

1. Give an example of a standard sorting algorithm that can be used when some of the values are not known until after the sorting has been started. Becky needs to sort a list of numbers into increasing order.
   She uses the following algorithm:
   STEP 1: Let \(L\) be the first value in the input list.
   Write this as the first value in the output list and delete it from the input list.
   STEP 2: If the input list is empty go to STEP 7.
   Otherwise let \(N\) be the new first value in the input list and delete this value from the input list. STEP 3: \(\quad\) Compare \(N\) with \(L\).
   STEP 4: If \(N\) is less than or equal to \(L\)
   • write the value of \(N\) immediately before \(L\) in the output list,
   • replace \(L\) with the first value in the new output list,
   • then go to STEP 2.
   STEP 5: If \(N\) is greater than \(L\)
   • if \(L\) is the value of the last number in the output list, go to STEP 6;
   • otherwise, replace \(L\) with the next value in the output list and then go to STEP 3.
   STEP 6: \(\quad\) Write the value of \(N\) immediately after \(L\) in the output list. Let \(L\) be the first value in the new output list and then go to STEP 2. STEP 7: Print the output list and STOP.
2. Trace through Becky's algorithm when the input list is $$\begin{array} { l l l l l l } 6 & 9 & 5 & 7 & 6 & 4 \end{array}$$ Complete the table in the Printed Answer Booklet, starting a new row each time that STEP 3 or STEP 7 is used.
   You should not need all the lines in the Answer Booklet. Becky measures the efficiency of her sort by counting using the number of times that STEP 3 is used.
3. 1. How many times did Becky use STEP 3 in sorting the list from part (b)?
   2. What is the greatest number of times that STEP 3 could be used in sorting a list of 6 values? A computer takes 15 seconds to sort a list of 60 numbers using Becky's algorithm.
4. Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?

14
8
13
6
4

10. & Freya
A binary search is to be performed on the names in the list above to locate the name Kim.

1. Explain why a binary search cannot be performed with the list in its present form.
2. Using an appropriate algorithm, alter 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.
3. Use the binary search algorithm to locate the name Kim in the list you obtained in (b). You must make your method clear.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-3_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
   1. Define the terms
      1. tree,
      2. minimum spanning tree.
         (3)
      3. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 1. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
         (3)
      4. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
   2. State whether your minimum spanning tree is unique. Justify your answer.
      (1)
      3. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-4_1492_1298_210_379} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} Figure 2 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
   3. Write down the inequalities that form region \(R\). The objective is to maximise \(3 x + y\).
   4. Find the optimal values of \(x\) and \(y\). You must make your method clear.
   5. Obtain the optimal value of the objective function. Given that integer values of \(x\) and \(y\) are now required,
   6. write down the optimal values of \(x\) and \(y\).
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_620_582_287_1098} \captionsetup{labelformat=empty} \caption{Figure 4}
      \end{figure} Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5. Figure 4 shows an initial matching.
      There are three possible alternating paths that start at A .
      One of them is $$A - 3 = R - 4 = C - 5$$
   7. Find the other two alternating paths that start at A .
   8. List the improved matching generated by using the alternating path \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5\).
   9. Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path used and your final matching.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-6_835_913_219_575} \captionsetup{labelformat=empty} \caption{Figure 5
      [0pt] [The total weight of the network is 98 km ]}
      \end{figure} Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe. A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.
   10. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   11. Write down a possible shortest inspection route, giving its length. It is now decided to start the inspection route at D . The route must still traverse each pipe at least once but may finish at any node.
   12. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.
       6. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-7_823_1374_226_347} \captionsetup{labelformat=empty} \caption{Figure 6}
       \end{figure} Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track.
   13. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
   14. Explain how you determined your shortest route from your labelled diagram. The track between E and F is now closed for resurfacing and cannot be used.
   15. Find the shortest route from A to H and state its length.
       (2)
       7. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-8_798_1497_258_283} \captionsetup{labelformat=empty} \caption{Figure 7}
       \end{figure} A project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   16. Complete the precedence table in the answer book.
       (3)
   17. Complete Diagram 1 in the answer book, to show the early event times and late event times.
   18. State the critical activities.
   19. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
   20. By considering the activities that must take place between time 7 and time 16, explain why it is not possible to complete this project with just 3 workers in the minimum time.
       8. A firm is planning to produce two types of radio, type A and type B. Market research suggests that, each week:
       Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week. The profit on each type A radio is \(\pounds 15\).
       The profit on each type B radio is \(\pounds 12\).
       The firm wishes to maximise its weekly profit.
       Formulate this situation as a linear programming problem, defining your variables.
       (Total 7 marks)

15
4
12
23
14

3 Let \(j\) equal 1.

3. \(\begin{array} { l l l l l l l l l l l } 1.8 & 1.4 & 2.6 & 1.6 & 2.8 & 0.9 & 3.1 & 0.8 & 1.2 & 2.4 & 0.6 \end{array}\) \section*{Question 3 continued} \section*{Question 3 continued} \section*{Question 3 continued}

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.

7. The numbers listed below are to be packed into bins of size \(n\), where \(n\) is a positive integer.
14
20
23
17
15
22
19
25

1 Use a Shell sort 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 } 37 & 25 & 16 & 12 & 36 & 24 & 13 & 11 \end{array}\) (5 marks) PART REFERENCE REFERENCE

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]

1. A gardener needs the following lengths of string. All lengths are in metres.
   0.4
   1.7
   1.3
   2.5
   2.1
   3.4
   4.3
   4.7
   5.1
   5.9
   6.1

She cuts the lengths from balls of string. Each ball contains 10 m of string.

1. Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear.
2. Use the first-fit bin packing algorithm to determine how the lengths could be cut from the balls of string.

2 Seven items need to be packed into bins. Each bin has capacity 30 kg . The sizes of the items, in kg, in the order that they are received, are as follows.
12
23
15
18
8
7
5

1. Find the packing that results using each of these algorithms.
   1. The next-fit method
   2. The first-fit method
   3. The first-fit decreasing method
2. A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists. Explain why the student is wrong. The bins of capacity 30 kg are replaced with bins of capacity \(M \mathrm {~kg}\), where \(M\) is an integer.
   The item of size 23 kg can be split into two items, of sizes \(x \mathrm {~kg}\) and \(( 23 - x ) \mathrm { kg }\), where \(x\) may be any integer value you choose from 1 to 11. No other item can be split.
3. Determine the smallest value of \(M\) for which four bins are needed to pack these eight items. Explain your reasoning carefully.

1. 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.
   Bubble sort is a quadratic order algorithm.
   A computer takes approximately 0.021 seconds to apply a bubble sort to a list of 2000 numbers.
2. Estimate the time it would take the computer to apply a bubble sort to a list of 50000 numbers. Make your method clear.

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.