Sort Algorithm Exam Questions
1. i. Describe how a merge sort differs from a bubble sort.
[4]
ii. Name two sorting algorithms, other than a bubble sort and merge sort.
[2]
2.
A games company has developed a game called Kidz Arrowz. The players throw an arrow at a
target board and are awarded different points depending on which circle the arrow lands. Fig. 1
shows the board.
Fig. 1
A computer program is required to keep track of the scores for each competition. The user will
enter the number of players, and the name of each player, in that competition to a maximum of
10.
i. The programmer has decided to use a bubble sort to sort the players’ scores in
descending order of score.
Describe the disadvantages of using a bubble sort.
[2]
ii. Despite the disadvantages, the programmer has decided to use a bubble sort for the
players’ scores.
Identify the characteristic of this problem that minimises the disadvantages of a bubble
sort.
[1]
iii. Write a procedure, sortScores, to perform a bubble sort on the global array scores to
sort the players’ scores into descending numeric order.
[6]
iv. An alternative sorting method is the insertion sort.
A procedure, insertionSort, has been written to sort an array numbers. The
procedure is incomplete.
Complete the procedure.
procedure insertionSort()
for count = 0 to [Link] - 1
position
= ........................................................
while position > 0 and numbers[position] < numbers[position-1]
temp
= .......................................................
numbers[position-1]
= ........................................
numbers[position] = temp
position
= ...................................................
endwhile
next count
endprocedure
3. A 1-dimensional array stores a set of numbered cards from 0 to 7. An example of this data is
shown in Fig in 4.1
* Two sorting algorithms the programmer could have used are a merge sort and bubble sort.
The worst case scenario for Merge is O(n log(n)) and for Bubble is O(n ^2).
Compare the use of a merge sort and a bubble sort on this array, evaluating the performance of
each sort, making reference to the worse case Big O notation.
[9]
4(a). A programmer needs to sort an array of numeric data using an insertion sort.
i. The following, incomplete, algorithm performs an insertion sort.
Complete the algorithm.
ii. Show how an insertion sort would sort the following data:
6 1 15 12 5 6 9
[6]
(b). i. Using Big-O notation state the best case complexity of insertion sort.
[1]
ii. Explain what your answer to part (b)(i) means.
[3]
5(a). The following pseudocode procedure performs an insertion sort on the array parameter.
01 procedure insertionSort(dataArray:byRef)
02 for i = 1 to [Link] - 1
03 temp = dataArray[i]
04 tempPos = i – 1
05 exit = false
06 while tempPos >= 0 and exit == false
07 if dataArray[tempPos] < temp then
08 dataArray[tempPos + 1] = dataArray[tempPos]
09 tempPos = tempPos - 1
10 else
11 exit = true
12 endif
13 endwhile
14 dataArray[tempPos + 1] = temp
15 next i
16 endprocedure
* Two sorting algorithms are merge sort and quick sort.
Compare the use of merge sort, quick sort and insertion sort on an array with a small number of
elements, and on an array with a very large number of elements.
You should make reference to the time complexities of each algorithm using the Big O notation in
your answer.
[9]
(b). Describe how a bubble sort will sort an array of 10 elements.
[6]
6. A programmer needs to sort an array of numeric data using an
insertion sort.
The number of data items in the array is continually
increasing.
Insertion sort has a worst case time complexity of O(n2) and
space complexity of O(1).
An alternative sorting algorithm that could be used is bubble
sort which also has a worst case time complexity of O(n2) and
space complexity of O(1).
Briefly outline how the bubble sort algorithm works. Discuss the
relationship between the complexities and the two sorting algorithms and
[9]
justify which of the two algorithms is best suited to sorting the array.
1. iii. Describe how a merge sort differs from a bubble sort.
[4]
iv. Name two sorting algorithms, other than a bubble sort and merge sort.
[2]
2.
A games company has developed a game called Kidz Arrowz. The players throw an arrow at a
target board and are awarded different points depending on which circle the arrow lands. Fig. 1
shows the board.
Fig. 1
A computer program is required to keep track of the scores for each competition. The user will
enter the number of players, and the name of each player, in that competition to a maximum of
10.
v. The programmer has decided to use a bubble sort to sort the players’ scores in
descending order of score.
Describe the disadvantages of using a bubble sort.
[2]
vi. Despite the disadvantages, the programmer has decided to use a bubble sort for the
players’ scores.
Identify the characteristic of this problem that minimises the disadvantages of a bubble
sort.
[1]
vii. Write a procedure, sortScores, to perform a bubble sort on the global array scores to
sort the players’ scores into descending numeric order.
[6]
viii. An alternative sorting method is the insertion sort.
A procedure, insertionSort, has been written to sort an array numbers. The
procedure is incomplete.
Complete the procedure.
procedure insertionSort()
for count = 0 to [Link] - 1
position
= ........................................................
while position > 0 and numbers[position] < numbers[position-1]
temp
= .......................................................
numbers[position-1]
= ........................................
numbers[position] = temp
position
= ...................................................
endwhile
next count
endprocedure
3. A 1-dimensional array stores a set of numbered cards from 0 to 7. An example of this data is
shown in Fig in 4.1
* Two sorting algorithms the programmer could have used are a merge sort and bubble sort.
The worst case scenario for Merge is O(n log(n)) and for Bubble is O(n ^2).
Compare the use of a merge sort and a bubble sort on this array, evaluating the performance of
each sort, making reference to the worse case Big O notation.
[9]
4(a). A programmer needs to sort an array of numeric data using an insertion sort.
iii. The following, incomplete, algorithm performs an insertion sort.
Complete the algorithm.
iv. Show how an insertion sort would sort the following data:
6 1 15 12 5 6 9
[6]
(b). iii. Using Big-O notation state the best case complexity of insertion sort.
[1]
iv. Explain what your answer to part (b)(i) means.
[3]
5(a). The following pseudocode procedure performs an insertion sort on the array parameter.
01 procedure insertionSort(dataArray:byRef)
02 for i = 1 to [Link] - 1
03 temp = dataArray[i]
04 tempPos = i – 1
05 exit = false
06 while tempPos >= 0 and exit == false
07 if dataArray[tempPos] < temp then
08 dataArray[tempPos + 1] = dataArray[tempPos]
09 tempPos = tempPos - 1
10 else
11 exit = true
12 endif
13 endwhile
14 dataArray[tempPos + 1] = temp
15 next i
16 endprocedure
* Two sorting algorithms are merge sort and quick sort.
Compare the use of merge sort, quick sort and insertion sort on an array with a small number of
elements, and on an array with a very large number of elements.
You should make reference to the time complexities of each algorithm using the Big O notation in
your answer.
[9]
(b). Describe how a bubble sort will sort an array of 10 elements.
[6]
6. A programmer needs to sort an array of numeric data using an insertion sort.
The number of data items in the array is continually increasing.
Insertion sort has a worst case time complexity of O(n2) and space complexity of O(1).
An alternative sorting algorithm that could be used is bubble sort which also has a worst case
time complexity of O(n2) and space complexity of O(1).
Briefly outline how the bubble sort algorithm works. Discuss the relationship between the
complexities and the two sorting algorithms and justify which of the two algorithms is best
[9]
suited to sorting the array.