do the program only in scratch programming.

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 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 project TM111_02_Q4.sb2. It contains three lists:

• school_1 andschool_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 blocks swapping_pass_1 and swapping_pass_2, and a when[1]key_pressed script. 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.

1. The swapping_pass_1 component and the when[1]key_pressed script 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 is school_1.

In a bubble sort, we perform a series of swapping 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, where n is the number of items.

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

Make sure the watcher for comparison_count is visible on the stage, then press the 1 key to execute the when[1]key_pressed script.

You should now see that the school_1 list 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 need to create a when[2]key_pressed that will result in the school_2 list being sorted. You can do this by copying the when[1]key_pressed script and carefully making the necessary changes.

Make sure the watcher forcomparison_count is visible on the stage, then run yourwhen[2]key_pressed script and note how

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

Note that you can repopulate the lists for the first and second schools, whenever required using the provided files school_1.txt and school_2.txt and following the procedure described on page 69 of Block 2, Book B, Part 4.

1. Next, need to 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, and 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 a when[m]key_pressed script that implements the algorithm above. 

1. Take a screenshot of your complete when[m]key_pressed script and paste it into your TMA document.

Run your when[m]key_pressed script and note how many comparisons were required. Add this number to the number of comparisons 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. 

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

 

1. In this part, you will look at some further examples of how Strategy 2 performs compared to Strategy 1.
   1. Merging two lists of length m and n respectively never needs more than m + n − 1 comparisons.

This is because each comparison results in an item being moved to the merged list. If there are m + n items altogether then if we ever got to m + 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 than m + n − 1 comparisons. 

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

1. How many comparisons would Strategy 1 take to sort a combined list of 23 items?
2. Considering Strategy 2, what is the greatest number of comparisons it could take to bubble sort the first and second lists individually, and then merge the results?

Comment briefly on the difference in performance.

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

Empty the merged list Initialise comparison_count to 0 Repeat until length of list school is O or length of list school_2 is 0 Increase comparison_count by I If item I of school is alphabetically before item I of school_2 Add item I of school to merged Remove this item from school If else Add item I of school_2 to merged Remove this item from school_2 of school is o Repeat until length of school_2 is 0 Add item of school 2 to merged Remove this item from school_2 length else Repeat until length of school is o Add item I of school to merged Remove this item from school