Sorting algorithms

17 8 16 12 24 19 23 11 20 13 4

The eleven numbers listed above 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 eleven numbers, the bins are packed as shown below.

Explain why this packing means that the value of n must be 40

The original list of eleven numbers is to be sorted into descending order.

Use a quick sort to obtain the fully sorted list. You must make your pivots clear.

Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40

The following algorithm determines the number of comparisons made when Prim’s algorithm is applied to K_n

Step 1 Start

Step 2 Input the value of n

Step 8 Let c = c + (ab) + (a – 1)

Step 9 If b 0 go to Step 6

Step 10 Output c

Step 11 Stop

For K₅, complete the table in the answer book to show the results obtained at each step of the algorithm.

The weights of the ten arcs in Figure 4 are

17 21 24 14 23 13 15 19 28 20

Starting at the left‑hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.

Find the total number of comparisons performed during the sort.

Find the maximum total number of comparisons required to sort the weights of the 10 arcs of K₅ into ascending order using bubble sort.

It is given that the maximum total number of comparisons required to sort the weights of the arcs of K_n into ascending order using bubble sort is

λn (n – 1)(n + 1)(n – 2)

where λ is a constant.

Determine the maximum total number of comparisons required to sort the weights of the arcs of K₅₀ into ascending order using bubble sort. You must make your method and working clear.

30 12 5 2 23 18 36 10 15 24

The list of ten numbers above 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.

The ten numbers 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 original list of ten numbers, the following allocation is obtained.

Bin 1: 30 12 2 Bin 2: 5 23 10 Bin 3: 18 15 Bin 4: 36 Bin 5: 24

Explain why the value of the integer n must be either 44 or 45

Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45

The nine distinct numbers in the following list are to be packed into bins of size 50

23 17 19 x 24 8 18 10 21

When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation.

Bin 1: 23 17 8

Bin 2: 19 x10

Bin 3: 24 18

Bin 4: 21

Explain why 13 x 21

The same list of numbers is to be sorted into descending order. 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 19 17 24 x 18 10 21 8

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

When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation.

Bin 1: 24 23

Bin 2: 21 19 10

Bin 3: 18 17 x

Bin 4: 8

Given that only one of the bins is full and that x is an integer,

calculate the value of x. You must give reasons for your answer.

2.1 1.7 3.0 1.9 3.2 1.2 3.3 1.4 1.5 0.2

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

The list of numbers is now to be sorted into descending order.

Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

For a list of n numbers, the quick sort algorithm has, on average, order n log n.

Given that it takes 2.32 seconds to run the algorithm when n = 450

calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when n = 11 250. You should make your method and working clear.