A harbour office uses a program to place container identification numbers into ascending order before a loading list is displayed. Table 1 shows six numbers...
Question 1 Report
A harbour office uses a program to place container identification numbers into ascending order before a loading list is displayed. Table 1 shows six numbers read from a data file. Fig. 1 shows one pass of an adjacent-swap sort algorithm. The box marked T is temporary storage. The code editor uses the word SWAP when the left number is larger than the right number.
| Position | Container number |
|---|---|
| 1 | 42 |
| 2 | 18 |
| 3 | 31 |
| 4 | 27 |
| 5 | 55 |
| 6 | 36 |
(a) Identify the first pair of numbers that causes a swap in Fig. 1. [1]
(b) Write the list after one complete left-to-right pass of the algorithm. [2]
(c) State the number that will be in the final position after this pass. [1]
Answer Details
(a) The first neighbouring pair that causes a swap is 42 and 18, because the left value is larger than the right value. [1]
(b) In an ascending adjacent-swap pass, compare from left to right and swap whenever the left value is larger:
\(42,18,31,27,55,36\)
\(\rightarrow 18,42,31,27,55,36\)
\(\rightarrow 18,31,42,27,55,36\)
\(\rightarrow 18,31,27,42,55,36\)
\(\rightarrow 18,31,27,42,36,55\)
The list after one complete pass is 18, 31, 27, 42, 36, 55. [2]
(c) The final position contains 55. [1] In this type of ascending pass, the largest value encountered is repeatedly moved rightwards.
Download The App On Google Playstore
Everything you need to excel in your exams
