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.$

DescriptionsFigure $1$

An OUBuild speech bubble containing the question 'What is $14$ times $3?\text{'}$

Back to $-$ Figure $1$

Figure $2$

A piece of paper, labelled Original word, is shown, containing the following characters printed in a row. metta. Below the piece of paper

is a row of clouds containing text. The first cloud is to the left of the piece of paper and contains the text Nenv word so far: $".$ Subsequent

clouds are each aligned with a character on the piece of paper above. The cloud below $m$ contains the text New word so far: $\text{'}mm\text{'}.$ The

cloud below e contains the text New word so far: 'mme'. The cloud below t contains the text New word so far: 'mmett'. The cloud below a

contains the text New word so far: 'mmetta'. The cloud below $1$ contains the text Neww word so far: 'mmettall'.

Back to $-$ Figure $2$

Figure $3$ Bubble sort versus exchange sort

A representation of bubble sort and exchange sort are shown. At the top of the picture there is a label saying 'Bubble sort' on

the left$-$hand side. On the right$-$hand side there is a label stating Pass and underneath the label in a vertical line are the

numbers $1,2$ and $3$ to represent separate passes of the algorithm. Next to each number are $6$ dots spread evenly out

horizontally across the page to represent each element to be compared. Between each dot is a curved line to show the

comparison between each pair of elements. There are $4$ dashed lines underneath the horizontal line.

At the bottom of the picture there is a label saying 'Exchange sort' on the left$-$hand side. On the right$-$hand side there is a label

stating Pass and underneath the label in a vertical line are the numbers $1,2$ and $3$ to represent separate passes of thealgorithm. Next to each number are $6$ dots spread evenly out horizontally across the page to represent each element to be

compared. On the horizontal line marked $1,$ there are $5$ lines all starting from the first element; each line is linked to a different

element, so there is a line between the first element and the second, then a line between the first element and the third, a line

between the first element and the fourth, a line between the first element and the fifth and a line between the first element and

the sixth.

On the horizontal line marked $2,$ there are $4$ lines all starting from the second element; each line is linked to a different element.

There is no line joining the first element. There is a line between the second element and the third, a line between the second

element and the fourth, a line between the second element and the fifth and a line between the second element and the sixth.

On the horizontal line marked $3,$ there are $3$ lines all starting from the third element; each line is linked to a different element.

There are no lines joining the first or second elements. There is a line between the third element and the fourth, a line between

the third element and the fifth and a line between the third element and the sixth. There are $4$ dashed lines underneath the

horizontal line.