In this part, you will find an expression for the number of comparisons made using oddeven sort to sort a list of length n, and compare its efficiency with bubble sort 1.

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 4 4 4 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 (4 4 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 5 5 5 matched dots and therefore (5 5 5) / 2 = 10 comparisons.

Generally, this pattern holds: for n items, there will be n n dots, and exactly n dots will be unmatched.

i.Write down an expression for the number of comparisons oddeven sort requires to sort n items.

ii.Use your expression to calculate how many comparisons oddeven sort requires to sort 100 items.

iii.The number of comparisons bubble sort 1 requires for n items is (n 1)². What conclusion can you draw about the relative efficiency of the two algorithms, bubble sort 1 versus oddeven sort?

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 oddeven 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 anothers way.

e. In this part, you will find an expression for the number of comparisons made using ov 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) Four rows, each of which depicts four dots. In the first row, labelled 'pass 1', dots 1 and 2 and dots 3 and 4 are connected with a horizontal line. In the second row, labelled 'pass 2', dots 2 and 3 are connected with a horizontal line; dots 1 and 4 are circled. In the third row, labelled 'pass 3 ', dots 1 and 2 and dots 3 and 4 are connected with a horizontal line. In the fourth row, labelled 'pass 4', dots 2 and 3 are connected with a horizontal line; dots 1 and 4 are circled. Figure 3(b) Five rows, each of which depicts five dots. In the first row, labelled 'pass 1 ', dots 1 and 2 and dots 3 and 4 are connected with a horizontal line; dot 5 is circled. In the second row, labelled 'pass 2', dot 1 is circled; dots 2 and 3 and dots 4 and 5 are connected with a horizontal line. In the third row, labelled 'pass 3 ', dots 1 and 2 and dots 3 and 4 are connected with a horizontal line; dot 5 is circled. In the fourth row, labelled 'pass 4 ', dot 1 is circled; dots 2 and 3 and dots 4 and 5 are connected with a horizontal line. In the fifth row, labelled 'pass 5', dots 1 and 2 and dots 3 and 4 are connected with a horizontal line; dot 5 is circled