Quick Sort Execution

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

1. $$\begin{array} { l l l l l l l l l l l } 4 & 6.5 & 7 & 1.3 & 2 & 5 & 1.5 & 6 & 4.5 & 6 & 1 \end{array}$$ The list of eleven numbers shown above is to be sorted into descending order.

1. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
2. Use the first-fit decreasing bin packing algorithm to pack the numbers into bins of size 10
3. Determine whether your answer to part (b) uses the minimum number of bins. You must justify your answer. A different list of eleven numbers is to be sorted into descending order using a bubble sort. The list after the second pass is
   1.6
   1.7
   1.5
   3.8
   3.3
   4.5
   4.8
   5.6
   5.4
   6.7
   9.1
4. Explain how you know that at least one of the first two passes of the bubble sort was not carried out correctly.

3 A set of ten cards have the following values: \(\begin{array} { l l l l l l l l l l } 13 & 8 & 4 & 20 & 12 & 15 & 3 & 2 & 10 & 8 \end{array}\) Kerenza wonders if there is a set of these cards with a total of exactly 50 .

1. Which type of problem (existence, construction, enumeration or optimisation) is this? The five cards \(4,8,8,10\) and 20 have a total of 50.
2. How many ways are there to arrange three of these five cards (with the two 8 s being indistinguishable) so that the total of the numbers on the first two cards is less than the number on the third card?
3. How many ways are there to select (choose) three of the five cards so that the total of the numbers on the three cards is less than 25 ?
4. Show how quicksort works by using it to sort the original list of ten cards into increasing order.
   You should indicate the pivots used and which values are already known to be in their correct position.

4. Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan

1. Use the quick sort algorithm to sort the above list into alphabetical order.
   (5)
2. Use the binary search algorithm to locate the name Louis.

2 Use the quicksort algorithm to rearrange the following numbers into ascending order. Indicate clearly the pivots that you use. $$\begin{array} { l l l l l l l l } 18 & 23 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$

\(650 \quad 431 \quad 245 \quad 643 \quad 455 \quad 134 \quad 710 \quad 234 \quad 162 \quad 452\)

1. The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. [5]

The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.

1. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.) [4]
2. Determine whether your solution to part (b) is optimal. Give a reason for your answer. [2]

The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper \((R)\), Palmer \((P)\), Boase \((B)\), Young \((Y)\), Thomas \((T)\), Kenney \((K)\), Morris \((M)\), Halliwell \((H)\), Wicker \((W)\), Garesalingam \((G)\).

1. Use the quick sort algorithm to sort the names above into alphabetical order. [5]
2. Use the binary search algorithm to locate the name Kenney. [4]

The table shows the marks obtained by students in a test. The students are listed in alphabetical order. Carry out a quick sort to produce a list of students in descending order of marks. You should show the result of each pass and identify your pivots clearly. (Total 5 marks)

Hajra	Vicky	Leisham	Alice	Nicky	June	Sharon	Tom	Paul
(H)	(V)	(L)	(A)	(N)	(J)	(S)	(T)	(P)

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

(Total 8 marks)

A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$150 \quad 104 \quad 200 \quad 60 \quad 184 \quad 84 \quad 120$$

1. Perform a quick sort to put the seven lengths in descending order. [4 marks]

The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.

1. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed. [4 marks]
2. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods. [1 mark]