August 2000
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 4

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 3
• Question 5
• Cover Page

Click to access
SUGGESTED SOLUTIONS
for Question 4

(a) Describe informally how a bubble sort works. [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]

(c) Give one advantage and one disadvantage of the bubble sort algorithm. [2 marks]

(d) Show the state of the following list after each pass of a bubble sort.
[13, 5, 7, 4, 1, 15]
[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]