The question needs to be implemented in OUBuild, so please, if you have the program, kindly help me answer the question with a screenshot.

Thank you

Please only OUBuild answers.

Question 4 (25 marks) This question focuses on Part 4 (repetition), Part 5 (components) and Part 6 (sorting). The teacher runs an after-school computing club. The school secretary has supplied a list of the names of children who plan to attend, in no particular order. The teacher wants to record the names in a list sorted in alphabetical order. She is familiar with bubble sort and has recently heard about an interesting variant called odd-even sort, which she believes might be more efficient and require fewer comparisons between names. She has asked you to investigate and provided an implementation of bubble sort which this question will guide you to adapt into an implementation of odd-even sort. Odd-even sort The odd-even sort algorithm is similar to bubble sort but has one crucial difference. Whereas bubble sort makes a series of swapping passes, comparing each pair of names in turn, oddeven sort uses odd passes and even passes. In an odd pass, it compares pairs of names in which the first name of the pair is at an odd position in the list, swapping if required. So, it compares the name at position 1 with the name at position 2, then the name at position 3 with the name at position 4, and so on. In an even pass, it compares pairs of names in which the first name of the pair is at an even position in the list, swapping if required. So, it compares the name at position 2 with the name at position 3 , then the name at position 4 with the name at position 5 , and so on. By making a series of alternately odd and even passes, the algorithm eventually arrives at a sorted list. For example, suppose we have this list in which, for simplicity, letters are used instead of names: We do an odd pass, comparing pairs of adjacent items where the first item is at an odd position: Two pairs are out of alphabetical order and are swapped, giving: Now we do an even pass, comparing pairs of adjacent items where the first item is at an even position: One pair is out of alphabetical order and is swapped, giving: We do an odd pass again: Two pairs are out of alphabetical order and are swapped, so we now have: We do an even pass again: One pair is out of alphabetical order and is swapped, so now we have: At this point, the list is sorted. It is possible to prove (but we won't do so here) that the list will always be sorted in at most n passes in total, where n is the length of the list. In the following parts, you will begin with an implementation of bubble sort 1, as discussed in Subsections 6.4.1 and 6.4.4 of Block 2 Part 6 and from it, gradually develop an implementation of odd-even sort. At the end, you will compare the efficiency of the two sorting methods by considering how many comparisons each makes when sorting lists of different lengths. Open the project TM111_02_Q4. sb2. It contains an implementation of bubble sort 1 which is almost identical to that developed in Block 2 Part 6 Activity 6.28. (There are some small implementation will also describe the algorithms involved in more detail here than was given in Part 6 , again to help you in this question.) Note that it contains: - the_list, an unsorted list of ten names - two components: the custom blocks do_swapping_pass and swap [] - a when[a]key_pressed script that sorts the_list - three variables: - position, used by do_swapping_pass - temp, used by swap[] - comparison_count, used to count the number of comparisons required to sort the_list. The algorithm implemented by the when[a]key_pressed script can be expressed as: Initialise comparison_count to 0 Repeat (length of the list - 1) times Do swapping pass The swapping passes are the responsibility of the custom block do_swapping_pass. The algorithm implemented by this component can be expressed as: Initialise position to I Repeat until (position is greater than (length of the list - 1)) If the item at position and the item at position +1 are in the wrong Swap them Increase comparison_count by I Increase position by I (We have used (position is greater than (length of the list - 1)) rather than (position - length of the_list) in preparation for what follows later.) The task of swapping two items is the responsibility of the custom block swap[]. Before progressing, make sure: - the_list is as initially provided. If it has been altered, then the original unsorted list is in the provided file first_list.txt. Import the contents of this file into the_list, following the procedure described on page 69 of Block 2 Part 4 - The watcher for comparison_count is visible on the stage. To get a feel for how the existing program works, run the when [a]key_pressed script. This should result in the_list being sorted, and the number of comparisons should be shown as 81 . You are going to create two new custom blocks, called do_odd_swapping_pass and do_even_swapping_pass. These do just what their names suggest: the first carries out an odd swapping pass, and the second an even swapping pass, as discussed in the description of odd-even sort above. As with do_swapping_pass, each counts the number of comparisons it makes. a. Before creating these components, you will plan how you will test them. Below we have started a table similar to Table 5.1 on page 158 of Block 2 Part 5 and filled in the first row with a possible test for do_odd_swapping_pass. For brevity, we have used a short list containing letters. Tests for do_odd_swapping_pass Copy this table into your TMA document and add to it two more tests that you would perform to check that the do_odd_swapping_pass component fulfils its specification. Then draw up a similar table, containing three suitable tests for the do_even_swapping_pass component. (5 marks) b. The definitions of the new custom blocks will be almost identical to that for do_swapping_pass. Look carefully at the do_swapping_pass definition and compare it with the algorithm given above, to make sure you understand how it works. The only differences in your new definitions will be that whereas in do_swapping_pass the variable position is initialised to 1 and then increased by 1 at the end of the loop: - in do_odd_swapping_pass the variable position should be initialised to 1 and then increased by 2 at the end of the loop (so, the pass will compare pairs of adjacent items where the first item is at an odd position in the list) - in do_even_swapping_pass the variable position should be initialised to 2 and then increased by 2 at the end of the loop (so, the pass will compare pairs of adjacent items where the first item is at an even position in the list). Create these custom blocks and their corresponding definitions. You should carry out the tests you specified in part (a), amending the contents of the_list, to ensure your blocks are working as required (though you are not required to provide evidence of this testing). Take a screenshot of each definition and paste them into your TMA document. (5 marks) c. Now create a when[b]key_pressed script to implement the odd-even sort algorithm which is as follows: Initialise comparison_count to 0 Initialise flag to odd Repeat (length of the list) times If flag is odd Do odd swapping pass Set flag to even else Do even swapping pass Set flag to odd You will need to create and use a variable, flag. The unsorted list we began with is stored in the file first_list.txt. Import the contents of this file into the_list, following the procedure described on page 69 of Block 2 Part 4. Then run your when [b] key_pressed script. This should result in the_list being sorted and the number of comparisons this time should be 45. Take a screenshot of your when[b] key_pressed script and paste it into your TMA document. (6 marks) d. We have provided two further lists of names, that is, second_list and third_list, which contain 15 and 20 names, respectively. Import each of these in turn and find out how many comparisons are needed to sort them, using the when [a]key_pressed bubble sort script, and noting the results. Then repeat the experiment, this time using the when [b]key_pressed odd-even sort script, again noting the results. Copy the following table into your TMA document and complete it. (4 marks) e. In this part, you will find an expression for the number of comparisons made using odd-even sort to sort a list of length n, and compare its efficiency with bubble sort 1. First consider the figure below. Figure 3(a) shows the four passes required to sort four items. The dots represent the items and the horizontal lines the comparisons between pairs of items. Notice that there are four rows of four dots and all the dots are matched with another dot, representing a comparison, except the four ringed ones. There are therefore 444 matched dots and each pair of dots corresponds to a comparison. So, we can divide this number by 2 to find that the number of comparisons is (44 4) /2=6. In a similar way, Figure 3 (b) shows the five passes required to sort five items. There are now five rows of five dots and all the dots are matched with another dot, except the five ringed ones. This means there are 555 matched dots and therefore (5 55)/2=10 comparisons. Generally, this pattern holds: for n items, there will be nn dots, and exactly n dots will be unmatched. i. Write down an expression for the number of comparisons odd-even sort requires to sort n items. ii. Use your expression to calculate how many comparisons odd-even sort requires to sort 100 items. iii. The number of comparisons bubble sort 1 requires for n items is (n1)2. What conclusion can you draw about the relative efficiency of the two algorithms, bubble sort 1 versus odd-even sort? (3 marks) f. Most modern processors have multiple cores - individual processing units that can operate in parallel. Imagine we wanted to program two cores so that they cooperated to sort a shared list using odd-even sort. This would not reduce the number of comparisons, but it would speed up the sorting because two cores between them can do twice the work that a single core can do in the same time. Suggest a way in which the sort could be carried out jointly by the two cores in such a way that both work on each pass but without getting in one another's way. (2 marks) Save your OUBuild project for Question 4 and submit it as TM111_02_Q4_PI. sb2 (where PI is your OU personal identifier, e.g. A1234567) in your TMA zip file. Alternatively, you may use your OUCU instead of your PI