Sorting algorithms

42 21 15 16 35 10 31 11 27 39

Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 65

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.

Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 65

The nine distinct numbers below are to be sorted into descending order 23 14 17 x 21 18 8 20 11 A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass, the list is 23 17 x 21 18 14 20 11 8 After the second complete pass, the list is 23 17 21 18 x 20 14 11 8

Using this information, write down the smallest interval that must contain x. Give your answer as an inequality.

59 45 18 55 47 11 63 17 15 42

The list of numbers above is to be sorted into descending order. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper wire is sold in one metre lengths.

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

Determine whether your solution to (b) is optimal. Give a reason for your answer.

18 29 48 9 42 31 37 24 27 41 The numbers above are Alan’s batting scores for the first 10 cricket matches of the season.

Use a quick sort to sort this list of numbers into ascending order. You must make your pivots clear.

Alan’s batting scores for the final 10 cricket matches of the same season were 72 53 89 91 68 67 90 77 83 75

Carry out a bubble sort on this second list of numbers to produce a list of these scores in ascending order. You need only give the state of the list after each pass.

Alan’s combined batting scores for the entire season were 9 18 24 27 29 31 37 41 42 48 53 67 68 72 75 77 83 89 90 91

Use the binary search algorithm to locate 68 in the combined list of 20 scores. You must make your method clear.

0.6 1.5 1.6 0.2 0.4 0.5 0.7 0.1 0.9 0.3

Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2.

The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear.

Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2.

Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.

1. Sam (S) 2. Janelle (J) 3. Haoyu (H) 4. Alfie (A) 5. Cyrus (C) 6. Komal (K) 7. Polly (P) 8. David (D) 9. Tom (T) 10. Lydia (L) A binary search is to be performed on the names in the list above to locate the name Lydia.

Using an appropriate algorithm, rearrange 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.

Use the binary search algorithm to locate the name Lydia in the list you obtained in (a). You must make your method clear.

A carpet fitter needs the following lengths, in metres, of carpet. 20 33 19 24 31 22 27 18 25 He cuts them from rolls of length 50 m.

Calculate a lower bound for the number of rolls he needs. You must make your method clear.

Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m.

Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.

Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.

1. Jenny 2. Merry 3. Charles 4. Ben 5. Toby 6. Hyo 7. Kim 8. Richard 9. Greg 10. Freya A binary search is to be performed on the names in the list above to locate the name Kim.

Explain why a binary search cannot be performed with the list in its present form.

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.

23 29 11 34 10 14 35 17 The numbers represent the sizes, in megabytes (MB), of eight files. The files are to be stored on 50 MB discs.

Calculate a lower bound for the number of discs needed to store all eight files.

Use the first-fit bin packing algorithm to fit the files onto the discs.

Perform a bubble sort on the numbers in the list to sort them into descending order. You need only write down the final result of each pass.

Use the first-fit decreasing bin packing algorithm to fit the files onto the discs.