Screenshot from my working attached please add scripts which should be added to the script from a screenshot.

If we just had a list of the three names

Tallulah, Juan, Ivan

the algorithm would compare Tallulah with Juan and because Juan comes before Tallulah alphabetically, they would be swapped, giving

Juan, Tallulah, Ivan OUBuild

File $r$

TM$111\_02\_$Q$4$

$\begin{array}{cc}compute{r}_c\text{l}\text{u}\text{b}& ?\\ 1& \text{D}\text{i}\text{y}\text{a}\\ 2& \text{A}\text{i}\text{d}\text{e}\text{n}\\ 3& \text{Q}\text{u}\text{i}\text{n}\text{l}\text{a}\text{n}\\ 4& \text{F}\text{a}\text{t}\text{i}\text{m}\text{a}\\ 5& \text{M}\text{e}\text{i}\\ 6& \text{S}\text{o}\text{l}\text{e}\text{d}\text{a}\text{d}\\ 7& Zoltan\\ 8& \text{O}\text{k}\text{s}\text{a}\text{n}\text{a}\\ 9& \text{I}\text{s}\text{l}\text{a}\\ 10& \text{U}\text{l}\text{r}\text{i}\text{k}\text{e}\\ +& \text{l}\text{e}\text{n}\text{g}\text{t}\text{h}\text{:}10\end{array}$

comparison$\_$count

$0$

position $1$

other$\_$position

$2$

$$

$\begin{array}{cc}\text{S}\text{c}\text{r}\text{i}\text{p}\text{t}\text{s}& \text{C}\text{o}\text{s}\text{t}\text{u}\text{m}\text{e}\text{s}\\ \text{M}\text{o}\text{t}\text{i}\text{o}\text{n}& \text{E}\text{o}\text{u}\text{n}\text{d}\text{s}\\ \text{L}\text{o}\text{o}\text{k}\text{s}& \text{C}\text{o}\text{n}\text{t}\text{r}\text{o}\text{l}\\ \text{S}\text{o}\text{u}\text{n}\text{d}& Sensing\\ \text{P}\text{e}\text{n}& \text{O}\text{p}\text{e}\text{r}\text{a}\text{t}\text{o}\text{r}\text{s}\\ \text{D}\text{a}\text{t}\text{a}& ?\\ \text{M}\text{a}\text{k}\text{e}\text{a}\text{V}\text{a}\text{r}\text{i}\text{a}\text{b}\text{l}\text{e}& ?\\ \text{g}\text{r}\text{a}\text{d}compariso{n}_c\text{o}\text{u}\text{n}\text{t}& ?\\ \text{g}\text{r}\text{a}\text{d}othe{r}_p\text{o}\text{s}\text{i}\text{t}\text{i}\text{o}\text{n}& ?\\ \text{g}\text{r}\text{a}\text{d}\text{p}\text{o}\text{s}\text{i}\text{t}\text{i}\text{o}\text{n}& ?\\ \text{g}\text{r}\text{a}\text{d}tmp& ?\\ \text{s}\text{e}\text{t}compariso{n}_c\text{o}\text{u}\text{n}\text{t}\text{g}\text{r}\text{a}\text{d}to0& ?\\ \text{c}\text{h}\text{a}\text{n}\text{g}\text{e}compariso{n}_c\text{o}\text{u}\text{n}\text{t}\text{g}\text{r}\text{a}\text{d}by& ?\end{array}$

$$

$$

r$-7.].$

N

show variable comparison$\_$count

hide variable comparison$\_$count

Sprites

New sprite:

Make a List

computer$\_$clubreplace item pos$1)$ of computer$\_$club grad with item pos$2$ of computer$\_$club gradreplace item pos$2$ of computer$\_$club grad with tmprepeat until $($position $=$ length of computer$\_$clubset other$\_$position grad to position $+1)$repeat until other$\_$position $=$ length of computer$\_$club $+1$If item position of computer$\_$club grad $)>$ item other$\_$position of computer$\_$club grad $)$ thenchange position grad by $1$add thing to computer$\_$club $$delete $17$ of computer$\_$club gradNew baddrop:insert thing at $1$grad of computer$\_$replace item $17$ of sqrt$"$ computer$\_$c "item $17$ of computer$\_$club $7$length of computer$\_$club $7$computer$\_$club grad contains thingshow list computer$\_$club $7$

Juan would then be compared with Ivan, which would need another swap. This would complete the first pass and we would have

Ivan, Tallulah, Juan

For the second pass we would start with Tallulah and compare it with Juan. Juan comes before Tallulah in alphabetical order, so they would be swapped. At the end of the second pass we would have

Ivan, Juan, Tallulah

and the list would now be sorted.

In this part you will investigate how many comparisons between list items exchange sort requires to sort some lists of different lengths.

i$.$To count the comparisons, we have provided a variable comparison$\_$count.

The only place where list items are compared is in the when$\_$green$\_$flag$\_$clicked script. Add a block to this script at an appropriate point to increment comparison$\_$count each time two list items are compared.

We are not quite done, because comparison$\_$count needs to be initialised to $0$ at the start of the when$\_$green$\_$flag$\_$clicked script, before we start the sort. Add a block to initialise comparison$\_$count at an appropriate point in the script.

Then make sure the watcher for comparison$\_$count is visible on the stage, and run the when$\_$green$\_$flag$\_$clicked script.

You should find that once the script has run the value of comparison$\_$count is $45.$

Take a screenshot

In this part you will explore the number of comparisons needed for exchange sort from a theoretical perspective.

Let n be the number of items to sort and consider the case n $=10.$

The $1$st item will be compared with the $2$nd$,3$rd$,4$th etc. item, and so on up to the $10$th item, a total of $9$ comparisons.

The $2$nd item will be compared with the $3$rd$,4$th$,5$th etc. item, and so on up to the $10$th item, a total of $8$ comparisons.

The $3$rd item will be compared with the $4$th$,5$th$,6$th etc. item, and so on up to the $10$th item, a total of $7$ comparisons.

The sort continues in this way until the $9$th item is reached. This is compared with the $10$th item, taking just $1$ comparison, and the algorithm will now finish.

This requires a total of $9+8+7+6+5+4+3+2+1$ comparisons. We could just add these $9$ numbers together but there is a neater way. You can probably see that their average is $10/2=5$ and as there are $9$ of them the total must be $9\backslash$times $5=45,$ just as we found in part $($d$)($i$).$

In the general case with n items the average will be n $/2$ and there will be n $1$ numbers, giving a total of $($n $1)\backslash$times n $/2$ comparisons.

i$.$How does the number of comparisons needed by exchange sort compare with that required by bubble sort $1?$

ii$.$ Although in the worst case bubble sort $3$ can require $($n $1)\backslash$times n $/2$ comparisons, the same as exchange sort, bubble sort $3$ has a particular feature that means it will generally take fewer comparisons. Explain what this feature is and describe what kind of data it makes bubble sort $3$ useful for sorting.