Sorting Algorithms (AQA GCSE Computer Science)

Exam Questions

30 mins9 questions
11 mark

Figure 13 shows an algorithm represented in pseudocode.

A developer wants to check the algorithm works correctly.

Line numbers are included but are not part of the algorithm.

Figure 13

1 arr[0] leftwards arrow 'c'
2 arr[1] leftwards arrow 'b'
3 arr[2] leftwards arrow 'a'
4 FOR i leftwards arrow 0 TO 1
5 FOR j leftwards arrow 0 TO 1
6 IF arr[j + 1] < arr[j] THEN
7 temp leftwards arrow arr[j]
8 arr[j] leftwards arrow arr[j + 1]
9 arr[j + 1] leftwards arrow temp
10 ENDIF
11 ENDFOR
12 ENDFOR

State the purpose of the algorithm.

Did this page help you?

21 mark

State one advantage of a merge sort over a bubble sort.

Did this page help you?

31 mark

State one disadvantage of a bubble sort over a merge sort.

Did this page help you?

15 marks

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.

A grid with five rows and six columns; numbers in the first row are 3, 5, 1, 4, 2 and in the last row are 1, 2, 3, 4, 5.

Did this page help you?

24 marks

Figure 7 shows a merge sort being carried out on a list.

Figure 7

Rectangles with numbers 42, 31, 52, 26 in various arrangements, showing different sequences one below the other.

Explain how the merge sort algorithm works.

Did this page help you?

33 marks

A program stores the following list of positive and negative numbers. The numbers need sorting into ascending order using a merge sort.

45

12

-99

100

-13

0

17

-27

The first step is to divide the list into individual lists of one number each. This has been done for you.

Complete the merge sort of the data by showing each step of the process.

Seven numbers inside individual boxes: 45, 12, -99, 100, -13, 0, 17, and -27. The boxes are arranged in a horizontal line.

Did this page help you?

4a4 marks

A library sorts their books based on a book code.

Show the steps that a merge sort would take to put the following list of book codes into ascending alphabetical order (from A to Z).

POE12 , BAC97 , FLY77 , JAV16 , TAL86 , AND18 , ZAR09 , HOP86

4b2 marks

Explain one advantage of a merge sort compared to a bubble sort.

Did this page help you?

14 marks

A program uses a file to store a list of words that can be used in a game.

A sample of this data is shown in Fig. 3.

crime

bait

fright

victory

nibble

loose

Fig. 3

Show the stages of a bubble sort when applied to data shown in Fig. 3.

Did this page help you?

25 marks

Describe the steps involved in performing a bubble sort on the list in Fig. 1. Show the state of the list after each complete pass through the list.

12

34

45

23

8

39

Fig. 1

Did this page help you?