|
(a) Describe informally how a bubble
sort works. [2 marks]
(a) • On each pass of the list adjacent
elements are compared; (1 mark)
• And swapped if they are not sorted with respect to each other;
(1 mark)
[2 marks]
(b) (i) State how many passes of a list
of size N it takes for bubble sort to ensure that the list is sorted
[1 mark]
(ii) State how many comparisons
must be performed on each pass. [1 mark]
(b) • (N-1) passes of the list; (1 mark)
• (N - i - the number of passes already performed) comparisons;
(1 mark)
[2 marks]
(c) Give one advantage and one disadvantage
of the bubble sort algorithm. [2 marks]
(c) • Advantage - we don’t need
to create another copy of the list; (1 mark)
• Disadvantage - if elements in the list are already sorted,
we still perform the
comparisons; (1 mark)
(d) Show the state of the following
list after each pass of a bubble sort.
[13, 5, 7, 4, 1, 15]
[4 marks]
(d) • 5, 7, 4, 1, 13, 15 (1 mark)
• 5, 4, 1, 7, 13, 15 (1 mark)
• 4, 1, 5, 7, 13, 15 (1 mark)
• 1, 4, 5, 7, 13, 15 (1 mark)
[4 marks]
(e) Implement the procedure BubbleSort,
the signature of which is given below, such that it takes a reference
to a list List and performs a bubble sort on the list. You may assume
that the length of the list is given by List.Length, the data values
in the list are stored in the array List.data, and the existence of
a procedure swap, which takes a reference to two elements in the list
and swaps them around.
PROCEDURE BubbleSort(VAR List: ListType); [5 marks]
(e) A sample definition of BubbleSort follows:
PROCEDURE BubbleSort(VAR List: Listtype);
Var pass, current : INTEGER;
flag : BOOLEAN;
Begin
pass:= 1;
flag:= false;
while pass< List.length and not flag do begin
flag:= true;
for current:= 1 to List.length - pass do begin
if list.data[current] > list.data[current+1]
then
begin
swap(list.data[current],
list.data[current+1]);
flag:=
false;
end
pass:= pass+1;
end;
end;
End;
And the following marking scheme should be used:
• Declaring an iterative structure to perform the passes; (1
mark)
• Declaring a second iterative structure to perform the comparisons;
(1 mark)
• Correctly bounds checking those loops; (1 mark)
• Comparing the adjacent elements on each iteration; (1 mark)
• Swapping the elements if necessary; (1 mark)
[5 marks]
|