7.03j Sorting: bubble sort and shuttle sort

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)

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

8 Four distinct positive integers are \(( 3 x - 5 ) , ( 2 x + 3 ) , ( x + 1 )\) and \(( 4 x - 13 )\).

1. Explain why \(x \geqslant 4\).
2. The four integers are to be sorted into ascending order using a bubble sort. The original list is \(\begin{array} { c c c c } ( 3 x - 5 ) & ( 2 x + 3 ) & ( x + 1 ) & ( 4 x - 13 ) \end{array}\) After the first pass, the list is \(( 3 x - 5 ) \quad ( x + 1 ) \quad ( 4 x - 13 ) \quad ( 2 x + 3 )\) After the second pass, the list is \(( x + 1 )\) \(( 4 x - 13 )\) \(( 3 x - 5 )\) \(( 2 x + 3 )\) After the third pass, the list is \(( 4 x - 13 ) \quad ( x + 1 )\) \(( 3 x - 5 )\) ( \(2 x + 3\) )
   1. By considering the list after the first pass, write down three inequalities in terms of \(x\).
   2. By considering the list after the second pass, write down two further inequalities in terms of \(x\).
   3. By considering the list after the third pass, write down one further inequality in terms of \(x\).
3. Hence, by considering the results above, find the value of \(x\).
   \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-19_2486_1714_221_153}

2

1. Use a Shell sort to arrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 7 & 8 & 1 & 6 & 3 & 4 & 5 & 2 \end{array}$$
2. Write down the number of comparisons on the first pass.

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 Five different integers are to be sorted into ascending order.

1. A bubble sort is to be used on the list of numbers \(\quad 6 \quad 4 \quad 5 \quad x \quad 2 \quad 11\).
   1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } 4 & x & 2 & 6 & 11 \end{array}$$ Write down an inequality that \(x\) must satisfy.
   2. After the second pass, the list becomes $$\begin{array} { l l l l l } x & 2 & 4 & 6 & 11 \end{array}$$ Write down a new inequality that \(x\) must satisfy.
2. The five integers are now written in a different order. A shuttle sort is to be used on the list of numbers \(\quad \begin{array} { l l l l l } 11 & x & 2 & 4 & 6 . \end{array}\)
   1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } x & 11 & 2 & 4 & 6 \end{array}$$ Write down an inequality that \(x\) must satisfy.
   2. After the second pass, the list becomes $$\begin{array} { l l l l l } 2 & x & 11 & 4 & 6 \end{array}$$ Write down a further inequality that \(x\) must satisfy.
3. Use your answers from parts (a) and (b) to write down the value of \(x\).

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.

1 Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l l } 6 & 5 & 9 & 4 & 5 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.

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]

3

1. Explain why it is impossible to draw a graph with exactly four vertices of orders 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
   A simply connected graph is one that is both simple and connected.
2. Explain why there is no simply connected graph with exactly four vertices of orders \(1,1,2\) and 4.
3. A connected graph has four vertices \(A , B , C\) and \(D\), in which \(A , B\) and \(C\) have order 2 and \(D\) has order 4. Explain how you know that the graph is Eulerian. Draw an example of such a graph and write down an Eulerian trail for your graph. A graph has three vertices, \(A , B\) and \(C\) of orders \(a , b\) and \(c\), respectively.
4. What restrictions on the values of \(a , b\) and \(c\) follow from the graph being
   1. simple,
   2. connected,
   3. semi-Eulerian?
      1. Describe carefully how to carry out the first pass through bubble sort when we are using it to sort a list of \(n\) numbers into increasing order. State which value is guaranteed to be in its correct final position after the first pass and hence explain how to carry out the second pass on a reduced list. Write down the stopping condition for bubble sort.
      2. Show the list of six values that results at the end of each pass when we use bubble sort to sort this list into increasing order. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$ You do not need to count the number of comparisons and the number of swaps that are used. Zack wants to cut lengths of wood from planks that are 20 feet long. The following lengths, in feet, are required. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$
      3. Use the first-fit method to find a way to cut the pieces.
      4. Use the first-fit decreasing method to find a way to cut the pieces. Give a reason why this might be a more useful cutting plan than that from part (iii).
      5. Find a more efficient way to cut the pieces. How many planks will Zack need with this cutting plan and how many cuts will he need to make? 5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel.
         1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z , \\ \text { subject to } & 3 x + 2 y - z \leqslant 14 , \\ & 2 x - 4 z \leqslant 7 , \\ & - 4 x + y \leqslant 4 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
         2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
            [0pt] [10]

1

1. Use shuttle sort to put this list of values into decreasing order (from largest to smallest). $$\begin{array} { l l l l l l l l l } 18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22 \end{array}$$ Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.
2. The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.
3. Suppose that some stronger boxes are available, each of which can hold at most \(W \mathrm {~kg}\). Find the least value of \(W\) for which only four boxes are needed. Show a packing using four of these stronger boxes.

3

1. Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.
2. The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step. Step 1: Input the original list and call it list A.
   Step 2: Remove the first item in list \(A\) and call this item \(X\).
   Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.
   Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.
   Step 5: If there are still items in list A, repeat Step 4.
   Step 6: Count the number of items in list \(\mathbf { B }\) and call this \(\mathbf { N }\).
   Step 7: Put the items in list B at positions 1 to N of list A, item X at position \(\mathrm { N } + 1\) of list A and the items in list C at positions \(\mathrm { N } + 2\) onwards of list A.
   Step 8: Display list A.

1 Owen and Hari each want to sort the following list of marks into decreasing order. $$\begin{array} { l l l l l l l l l l } 31 & 28 & 75 & 87 & 42 & 43 & 70 & 56 & 61 & 95 \end{array}$$

1. Owen uses bubble sort, starting from the left-hand end of the list.
   1. Show the result of the first pass through the list. Record the number of comparisons and the number of swaps used in this first pass. Which marks, if any, are guaranteed to be in their correct final positions after the first pass?
   2. Write down the list at the end of the second pass of bubble sort.
   3. How many more passes are needed to get the value 95 to the start of the list?
   4. Hari uses shuttle sort, starting from the left-hand end of the list. Show the results of the first and the second pass through the list. Record the number of comparisons and the number of swaps used in each of these passes.
   5. Explain why, for this particular list, the total number of comparisons will be greater using bubble sort than using shuttle sort. Shuttle sort is a quadratic order algorithm.
   6. If it takes Hari 20 seconds to sort a list of ten marks using shuttle sort, approximately how long will it take Hari to sort a list of fifty marks?

1 The list below is to be sorted into increasing order using bubble sort, starting at the left-hand end of the list. $$\begin{array} { l l l l l l } 24 & 57 & 9 & 31 & 16 & 4 \end{array}$$

1. Show which values are compared and which are swapped in the first pass. Write down the list that results at the end of the first pass.
2. Without showing the individual comparisons and swaps, write down the lists that result after the second pass and after the third pass.
3. In total there will be five passes made in carrying out bubble sort on the list. Write down how many swaps are made in each pass.

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 .

2. (a) The following list of numbers is to be sorted into descending order. $$\begin{array} { l l l l l l } 35 & 23 & 10 & 46 & 24 & 11 \end{array}$$ Use the Bubble sort algorithm to obtain a sorted list, giving the state of the list at each stage where two values could be interchanged.
(b) Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
(c) Use the first-fit decreasing algorithm to fit the data in part (a) into bins of size 50. Explain how you decided in which bin to place the number 11.

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

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.

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