do the program only in scratch programming. The teacher runs an after-school computing club and stores the

Fantastic news! We've Found the answer you've been seeking!

Question:

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.

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

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.

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.