User interface language: English | Español

Date May 2019 Marks available 1 Reference code 19M.1.HL.TZ0.15
Level HL Paper 1 Time zone no time zone
Command term State Question number 15 Adapted from N/A

Question

A school teacher decides to write a program to store class records and marks. Part of this program involves using a sort algorithm. The algorithm shown is a selection sort and to test it, the teacher has set up an array VALUES[] with 5 elements of test data.

LIMIT = 4

loop COUNTER1 from 0 to LIMIT – 1
MINIMUM = COUNTER1

loop COUNTER2 from COUNTER1 + 1 to LIMIT
if VALUES[COUNTER2] < VALUES[MINIMUM] then
MINIMUM = COUNTER2
end if
end loop

if MINIMUM ≠ COUNTER1 then
TEMPORARY = VALUES[MINIMUM]
VALUES[MINIMUM] = VALUES[COUNTER1]
VALUES[COUNTER1] = TEMPORARY
end if

end loop

 

Copy and complete the table below to trace the algorithm using the data set:
20, 6, 38, 50, 40

[5]
a.

With reference to the algorithm in the flow chart, construct this algorithm in pseudocode so that it performs the same function.

[3]
b.i.

State the type of sort in the algorithm constructed in b(i).

[1]
b.ii.

Construct an algorithm fragment to output the data in the array VALUES[]

[2]
c.

Markscheme

Award [5 max].
Both COUNTER1 and COUNTER2 correct;
MINIMUM column correct;
Final VALUES[] 0, 1, 2 correct;
Final VALUES[] 3, 4 correct;
TEMPORARY column correct;

Note to examiners:
Allow follow through (FT).
In case of different representation of values in columns COUNTER1 and COUNTER2, then FT, award marks for the correct values of the variables MINIMUM and TEMPORARY.

a.

Award [3 max].
Use of correct nested loops;
Correct use of flag;
Inner loop checking adjacent cells;
Values being swapped if necessary;

Example algorithm 1:

LIMIT = 4
FLAG = TRUE
loop while FLAG = TRUE
FLAG = FALSE
loop COUNTER from 0 to LIMIT - 1
if VALUES[COUNTER] > VALUES[COUNTER + 1] then
TEMPORARY = VALUES[COUNTER]
VALUES[COUNTER] = VALUES[COUNTER + 1]
VALUES[COUNTER + 1] = TEMPORARY
FLAG = TRUE
end if
end loop
end loop

A recursive solution is allowed at HL. SL candidates who submit an above level recursive solution should also receive credit.

Version 1 – basic recursive solution

Award [3 max].
BUBBLESORT defined as a procedure with correct pass through parameters and end/return statement;
Correct loop with values swapped if necessary inside procedure;
Recursive call of BUBBLESORT with parameters passed;
Correct condition for recursive call;

Example algorithm 2

LIMIT = 4
BUBBLESORT(VALUES, LIMIT)
loop COUNTER from 0 to LIMIT - 1
if VALUES[COUNTER] > VALUES[COUNTER + 1] then
TEMPORARY = VALUES[COUNTER]
VALUES[COUNTER] = VALUES[COUNTER + 1]
VALUES[COUNTER + 1] = TEMPORARY
end if
end loop
if LIMIT – 1 > 1 then
call BUBBLESORT(VALUES, LIMIT - 1)
end if
end BUBBLESORT

Version 2 – more efficient recursive solution

Award [3 max].
BUBBLESORT defined as a procedure with correct pass through
parameters and end/return statement;
Correct loop with values swapped if necessary inside procedure;
Recursive call of BUBBLESORT with parameters passed;
Correct condition for recursive call;
Correct use of flag;

Example algorithm 2

LIMIT = 4
BUBBLESORT(VALUES, LIMIT)
FLAG = FALSE
loop COUNTER from 0 to LIMIT - 1
if VALUES[COUNTER] > VALUES[COUNTER + 1] then
TEMPORARY = VALUES[COUNTER]
VALUES[COUNTER] = VALUES[COUNTER + 1]
VALUES[COUNTER + 1] = TEMPORARY
FLAG = TRUE
end if
end loop
if LIMIT – 1 > 1 and FLAG = TRUE then
call BUBBLESORT(VALUES, LIMIT - 1)
end if
end BUBBLESORT
b.i.

Bubblesort;

b.ii.

Award [2 max].
Use of (any type of) loop;
Correct output statement;

Example algorithm:

loop COUNTER from 0 to LIMIT
   output VALUES[COUNTER]
end loop
c.

Examiners report

Those candidates who are proficient in programming easily got full marks. The others did not complete the exercise or completed it incorrectly.

a.
[N/A]
b.i.
[N/A]
b.ii.
[N/A]
c.

Syllabus sections

Topic 4: Computational thinking, problem-solving and programming » 4.2 Connecting computational thinking and program design
Show 59 related questions
Topic 4: Computational thinking, problem-solving and programming

View options