Name: ________________________
sorting algorithms
Class: ________________________
Date: ________________________
Time: 49 minutes
Marks: 44 marks
Comments:
Page 1 of 7
Q1.
The algorithm below is a sorting algorithm.
• Array indexing starts at 0.
• Line numbers are included but are not part of the algorithm.
1 arr ← [4, 1, 6]
2 swapsMade ← false
3 WHILE swapsMade = false
4 swapsMade ← true
5 i ← 0
6 WHILE i < 2
7 IF arr[i+1] < arr[i] THEN
8 t ← arr[i]
9 arr[i] ← arr[i+1]
10 arr[i+1] ← t
11 swapsMade ← false
12 ENDIF
13 i ← i + 1
14 ENDWHILE
15 ENDWHILE
(a) State the data type of the variable swapsMade in the algorithm shown above.
___________________________________________________________________
(1)
(b) The identifier swapsMade is used in the algorithm shown above.
Explain why this is a better choice than using the identifier s.
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(2)
(c) Shade one lozenge to show which of the following contains the false statement
about the algorithm.
A The algorithm uses a named constant.
B The algorithm uses indefinite iteration.
C The algorithm uses nested iteration.
(1)
(d) Complete the trace table for the algorithm shown above. Some values have already
been entered.
Page 2 of 7
arr
swawpsMade i t
[0] [1] [2]
4 1 6 false
(6)
(Total 10 marks)
Q2.
Fill in the blank arrays to show the steps involved in applying the bubble sort algorithm to
the array [3, 5, 1, 4, 2]. You only need to show the missing steps where a change is
applied to the array.
3 5 1 4 2
1 2 3 4 5
(Total 5 marks)
Q3.
The algorithm below is a sorting algorithm.
• Array indexing starts at 0.
• Line numbers are included but are not part of the algorithm.
Page 3 of 7
1 arr ← [4, 1, 6]
2 sorted ← false
3 WHILE sorted = false
4 sorted ← true
5 i ← 0
6 WHILE i < 2
7 IF arr[i+1] < arr[i] THEN
8 t ← arr[i]
9 arr[i] ← arr[i+1]
10 arr[i+1] ← t
11 sorted ← false
12 ENDIF
13 i ← i + 1
14 ENDWHILE
15 ENDWHILE
(a) State the data type of the variable sorted in the algorithm shown above.
___________________________________________________________________
(1)
(b) The identifier sorted is used in the algorithm shown above.
Explain why this is a better choice than using the identifier s.
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(2)
(c) Shade one lozenge to show which of the following contains the false statement
about the algorithm above.
A The algorithm uses a named constant
B The algorithm uses indefinite iteration
C The algorithm uses nested iteration
(1)
(d) Complete the trace table for the algorithm shown above. Some values have already
been entered.
arr
sorted i t
[0] [1] [2]
4 1 6 false
Page 4 of 7
(6)
(e) Fill in the values in the boxes to show how the merge part of the merge sort
algorithm operates. The first and last rows have been completed for you.
(3)
(f) State one advantage of the merge sort algorithm compared to the sorting algorithm
in Figure 2.
___________________________________________________________________
___________________________________________________________________
(1)
(g) A programmer implementing the algorithm in Figure 2 decided to create it as a
subroutine. Line 1 was removed and the array arr was made a parameter of the
subroutine.
State two reasons why the programmer decided to implement the algorithm as a
subroutine.
Reason 1 ___________________________________________________________
___________________________________________________________________
Page 5 of 7
Reason 2 ___________________________________________________________
___________________________________________________________________
(2)
(Total 16 marks)
Q4.
The image below shows a merge sort being carried out on a list.
Merge sort being carried out on list
The sort is carried out in two phases. The phases are separated by the dotted line.
(a) Explain the process that is being carried out in Phase 1 of the sort (above the dotted
line).
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(3)
(b) Explain the process that is being carried out in Phase 2 of the sort (below the dotted
line).
___________________________________________________________________
___________________________________________________________________
Page 6 of 7
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
(3)
(Total 6 marks)
Q5.
State one advantage and one disadvantage of merge sort when compared to bubble sort.
Advantage: _____________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
Disadvantage: ___________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
(Total 2 marks)
Q6.
Fill in the blank arrays to show the steps involved in applying the bubble sort algorithm to
this array [3, 5, 1, 4, 2] . You need only show the missing steps where a change is
applied to the array:
3 5 1 4 2
1 2 3 4 5
(Total 5 marks)
Page 7 of 7
