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 and stores the names of children who belong to this club in a list, which at present is unsorted.

She is considering ways to sort the list and is interested in a sorting algorithm she has recently heard about and which is new to her. The algorithm is called exchange sort, and she explains it like this.

In the first pass through the list you compare the name at position $1$ with that at position $2$: if they are out of order then you swap them. Then you compare the name at position $1$ with that at position $3$: if they are out of order then you swap them, and so on for the names at positions $4,5$ etc. You continue in this way until the name at position $1$ has been compared with the name at all other positions and swapped whenever necessary. When the first pass is complete the name that ends up at position $1$ will be the first in alphabetical order.

The second pass is similar, except that you begin with the name at position $2,$ comparing it with the names at positions $3,4$ etc. When pass two is complete the names at $1$ and $2$ will be the first and second in alphabetical order.

In the third pass you compare the name at position $3$ with those at positions $4,5$ etc. When pass three is complete the names at $1,2$ and $3$ will be the first, second and third in alphabetical order.

Continuing in this way we will eventually compare the name in the next$-$to$-$last position with that in the last position, swapping them if necessary, and at that point the entire list will be sorted.

This might sound a bit like bubble sort at first but if you look at the pairs that are compared in the first pass you can see that the pattern of comparisons is quite different, as illustrated in Figure $3.$

Described image

Figure $3$ Bubble sort versus exchange sort

Figure $3$ Bubble sort versus exchange sort

So for example 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

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.

The teacher has begun writing a program to implement exchange sort 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.

a$.$As a warm$-$up to get a feel for how the algorithm works, suppose we want to sort the following list of names alphabetically:

Ira, Noah, Jabari, Thor, Ari

Write what the list will look like after:

the first pass

the second pass

the third pass

the fourth pass.

You may find it useful to write the names on slips of paper or on sticky notes.

$(4$ marks$)$