|
Do
not award half marks. Do not deduct marks for trivial syntactic errors.
Alternative correct answers should be given credit, unless otherwise
indicated in the marking scheme.
(a)(i)Briefly describe the selection
sort algorithm.[2 marks ]
(ii)Briefly describe the bubble sort algorithm.[2 marks ]
(iii)State which of these two technique will be required to perform
fewer
comparison in a worst-case scenario.[1 mark ]
(i)Selection sort:
• Moves the first item in the list that has not been sorted to
the first unsorted
position;(1 mark)
• By swapping the two values around.(1 mark)
[2 marks ]
(ii)A bubble sort
• Iterates over the list comparing adjacent elements;(1 mark)
• Swapping the two if the order requires it.(1 mark)
[2 marks ]
(iii)Selection sort [1mark ]
(b)The procedure SelectionSort takes an unsorted list x and sorts
the list into
ascending order.Show the state of the list given below on each pass
of the procedure SelectionSort
26 3 25 17 6 40 39
[5 marks ]
• 26 3
1 25 17 6 40 39
• 1 26 3 25 17 6 40 39 (1 mark)
• 1 3 26 25 17 6 40 39 (1 mark)
• 1 3 6 25 1726 40 39 (1 mark)
• 1 3 6 17 25 26 40 39 (1 mark)
• 1 3 6 17 25 26 39 40 (1 mark)
Do not deduct marks for consequential error. [5 marks ]
(c)Define the procedure SelectionSort the signature of which is given
below,which takes a list x which is an array of integers of length
ListSize and performs a selection sort on x such that the items are
placed in ascending order.
PROCEDURE SelectionSort(VAR x : ListType; ListSize : INTEGER);
[5 marks ]
A sample definition
of SelectionSort follows:
PROCEDURE SelectionSort(VAR x : ListType; ListSize : INTEGER);
VAR i, j, least, index: INTEGER;
BEGIN
FOR i:= 1 TO ListSize-1 DO BEGIN
least:= x[i];
FOR j:= i+1 TO ListSize DO BEGIN
IF x[j] < least
THEN least:= x[j];
index:= j;
END;
x[index]:= x[i];
x[i]:= least;
END;
END;
And the following marking scheme should be used:
• Declaring an outer loop,bounded 1 to ListSize-1 (1 mark)
• Declaring an inner loop,bounded i+1 to ListSize (1 mark)
• Setting least to the value x[i];(1 mark)
• And re-setting it to x[j] should x[j] be smaller;(1 mark)
• Swapping the values of x[i] and x[index] on each iteration
of the outer loop.
(1 mark)
[5 marks ]
|