The teacher runs an after-school computing club and stores the names of children who belong to this club in a list, which at present is unsorted.

Another school close by would like to offer a computer club, but does not have suitable facilities. However, the two schools have reached an agreement allowing children from the second school to attend the computer club run by the first.

The second school has supplied a list, again unsorted, of the names of children from that school who want to belong to the club.

The teacher who runs the club now wants a program that will take the two lists and combine them to eventually produce a single sorted list containing the names of all the children, from both schools, who belong to the club.

She is considering two possible strategies for producing this list.

Strategy 1. Append the second school's unsorted list to the end of the first school's unsorted list, then sort the combined list.

Strategy 2. Sort the two lists separately, then combine the sorted lists in a way that results in a single sorted list.

The teacher is interested in exploring how many comparisons between names each sorting strategy uses and which of the two requires the fewer comparisons. She has begun writing a program to investigate these questions and has enlisted you to help her complete it and use it to run some experiments.

For simplicity, we will only use the children's first names and assume no two names are the same.

Open the projectTM111_02_Q4.sb2. It contains three lists:

• school_1andschool_2, which contain the two unsorted lists from the first and second schools, respectively
• merged, which is empty at present; this will hold the final sorted list.

There are also four variables, as follows (the meaning of 'swapping pass' will be described when we come to it):

• pass, used to keep track of swapping passes
• position, used to keep track of the current position in a swapping pass
• temp, used when swapping two adjacent elements
• comparison count, used to count how many pairs of adjacent elements are compared, during sorting and the subsequent merge operation.

In addition there are two components, the custom blocksswapping_pass_1andswapping_pass_2, and awhen[1]key pressedscript. The purpose of these will now be explained.

Note that there is no need for you to modify either of the custom blocks and you should not attempt to do so.

a. Theswapping_pass_1component and thewhen[1]key_ pressedscript together form an implementation of bubble sort 2, as discussed in Subsection 6.4.2 of Block 2 Part 6. The list they will sort isschool_1.

In a bubble sort we perform a series ofswapping passes, where each swapping pass consists of working our way through the list to be sorted, comparing pairs of adjacent items, and swapping any pair that is out of order.

Each swapping pass causes an item to 'bubble up' and stop at its correct position in the sorted list and so after each swapping pass the unsorted portion of the list becomes one item shorter. Since a swapping pass only needs to consider the unsorted portion, each pass can be one comparison shorter than the previous one.

This is illustrated in Figures 6.34 to 6.37 of Subsection 6.4.2, where we observe that bubble sort 2 will require approximately (n 1)²/2 comparisons, wherenis the number of items.

It is not too hard to show (but we will just assume this result) that the exact number isn (n 1)/2.

Make sure the watcher forcomparison countis visible on the stage, then press the 1 key to execute thewhen[1]key pressedscript.

You should now see that theschool_1list is sorted, and 66 comparisons were needed. This is the expected number: the length of the list is 12 and 12 11 / 2 = 66.

Now create awhen[2]key pressedthat will result in theschool_2list being sorted. You can do this by copying thewhen[1]key pressedscript and carefully making the necessary changes.

i. Take a screenshot of yourwhen[2]key pressedscript and paste it into your TMA document.

ii. Make sure the watcher forcomparison countis visible on the stage, then run yourwhen[2]key pressedscript and note how many comparisons were required. Explain what number you were expecting and why, and state whether the result of running the script agrees with your calculation.

b. Next you will write a script to merge the two sorted lists. The idea behind the merging algorithm is that we repeatedly compare the item at the front of the first list with the item at the front of the second list: whichever is the smaller is added to the merged list, then removed from its original list. At some point, one list will become empty and we can then simply append the contents of the other list to the merged list.

The steps of the algorithm are as follows, including the steps that are there to count the number of times two items are compared.

Create awhen[m]key pressedscript that implements the algorithm above.

i Take a screenshot of your completewhen[m]key pressedscript and paste it into your TMA document.

ii. Run yourwhen[m]key pressedscript and note how many comparisons were required. Add this number to the numbers of comparisons that were required to sort the individual lists in part (a), to get the total number of comparisons taken to generate the final sorted list of children from both schools.

iii.Suppose that instead of following Strategy 2 (sorting the lists then merging the results) we had instead used Strategy 1 (appending the second list to the first and then sorting the combined list using bubble sort 2). Use the formula given earlier to calculate how many comparisons would have been needed and briefly comment on which of the two strategies seems to be the most efficient in this example.

(15 marks)

c. In this part, you will look at some further examples of how Strategy 2 performs compared to Strategy 1.

i. Merging two lists of lengthmandnrespectively never needs more thanm+n 1 comparisons.

This is because each comparison results in an item being moved to the merged list. If there arem+nitems altogether then if we ever got tom+n 1 comparisons it would mean we had moved all but one of the items to the merged list and the final item could be moved without any comparison.

This is the worst case; in general we are likely to need fewer thanm+n 1 comparisons.

Suppose the first list contained 18 items and the second list contained 5 items.

• How many comparisons would Strategy 1 take to sort a combined list of 23 items?

Considering Strategy 2, what is the greatest number of comparisons it could take to bubble sort the first and second lists individually, then merge the results?

Comment briefly on the difference in performance.

ii. Is Strategy 2 always an improvement on Strategy 1? Consider an extreme case. Suppose the first list has only 1 item and the second list has 18 items. Following the same method as in part (i) above, calculate the maximum number of comparisons required by each strategy and comment briefly on what you find.

(5 marks)