7.03j Sorting: bubble sort and shuttle sort

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.

2

1. Use a shuttle sort to rearrange into alphabetical order the following list of names:
   Rob, Eve, Meg, lan, Xavi
   Show the list at the end of each pass.
2. A list of ten numbers is sorted into ascending order, using a shuttle sort.
   1. How many passes are needed?
   2. Give the maximum number of comparisons needed in the sixth pass.
   3. Given that the list is initially in descending order, find the total number of swaps needed.
      [0pt] [4 marks]

2 The instructions labelled 1 to 7 describe the steps of a sorting algorithm applied to a list of six numbers.
1 Let \(i\) equal 1.
2 Repeat lines 3 to 7, stopping when \(i\) becomes 6 .

3 Let \(j\) equal 1.

4 Repeat lines 5 and 6 , until \(j\) becomes \(7 - i\).

5 If the \(j\) th number in the list is bigger than the \(( j + 1 )\) th, then swap them.

6 Let the new value of \(j\) be \(j + 1\).

2 In an investigation into a burglary, Agatha has five suspects who were all known to have been near the scene of the crime, each at a different time of the day. She collects evidence from witnesses and draws up a table showing the number of witnesses claiming sight of each suspect near the scene of the crime at each possible time. Suspect \begin{table}[h] \end{table}

1. Use the Hungarian algorithm on a suitably modified table, reducing rows first, to find the matchings for which the total number of claimed sightings is maximised. Show your working clearly. Write down the resulting matchings between the suspects and the times. Further enquiries show that the burglary took place at 5 pm , and that Dr Silverbirch was not the burglar.
2. Who should Agatha suspect?

2. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances. Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.

1. Four sales representatives ( \(R _ { 1 } , R _ { 2 } , R _ { 3 }\) and \(R _ { 4 }\) ) are to be sent to four areas ( \(A _ { 1 } , A _ { 2 } , A _ { 3 }\) and \(A _ { 4 }\) ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below.

Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.

1. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

• strip the wallpaper,
• paint the woodwork and ceiling,
• hang the new wallpaper,
• replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job. As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
2. Hence find the minimum time in which the friends can redecorate the lounge.
   

12.1 \quad 9.3 \quad 15.7 \quad 10.9 \quad 17.4 \quad 6.4 \quad 20.1 \quad 7.9 \quad 8.1 \quad 14.0

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 \hfill [3]

The list is to be sorted into descending order.

1. 1. Starting at the left-hand end of the list, perform two passes through the list using a bubble sort. Write down the state of the list that results at the end of each pass.
   2. Write down the total number of comparisons and the total number of swaps performed during your two passes.
   \hfill [4]
2. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear. \hfill [4]
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33 \hfill [3]
4. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer. \hfill [1]

25 22 30 18 29 21 27 21 The list of numbers above is to be sorted into descending order.

1. 1. Perform the first pass of a bubble sort, giving the state of the list after each exchange.
   2. Perform further passes, giving the state of the list after each pass, until the algorithm terminates.
   [5]

The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm.

1. 1. Show the result of applying the first fit decreasing bin packing algorithm to this situation.
   2. Determine whether your solution to \((b)\) \((i)\) has used the minimum number of 50 cm rods.
   [4]

1. Glasgow
2. Newcastle
3. Manchester
4. York
5. Leicester
6. Birmingham
7. Cardiff
8. Exeter
9. Southampton
10. Plymouth

A binary search is to be performed on the names in the list above to locate the name Newcastle.

1. Explain why a binary search cannot be performed with the list in its present form. [1]
2. Using an appropriate algorithm, alter the list so that a binary search can be performed. State the name of the algorithm you use. [4]
3. Use the binary search algorithm on your new list to locate the name Newcastle. [4]

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]

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)

Tom has some packages that he needs to sort into order of decreasing weight. The weights, in kg, given on the packages are as follows. 3 \quad 6 \quad 2 \quad 6 \quad 5 \quad 7 \quad 1 \quad 4 \quad 9 Use shuttle sort to put the weights into decreasing order (from largest to smallest). 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. Write down the total number of passes, the total number of comparisons and the total number of swaps used. [6]

The following algorithm is a version of bubble sort. Step 1 \quad Store the values to be sorted in locations L(1), L(2), \(\ldots\) , L(n) and set i to be the number, n, of values to be sorted. Step 2 \quad Set j = 1. Step 3 \quad Compare the values in locations L(j) and L(j+1) and swap them if that in L(j) is larger than that in L(j+1). Step 4 \quad Add 1 to j. Step 5 \quad If j is less than i then go to step 3. Step 5 \quad Write out the current list, L(1), L(2), \(\ldots\) , L(n). Step 6 \quad Subtract 1 from i. Step 7 \quad If i is larger than 1 then go to step 2. Step 8 \quad Stop.

1. Apply this algorithm to sort the following list. 109 \quad 32 \quad 3 \quad 523 \quad 58. Count the number of comparisons and the number of swaps which you make in applying the algorithm. [4]
2. Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number. [2]
3. Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100 000 values? (Give your answer in hours and minutes.) [2]