Identify two variables that have been used in the algorithm.

Copy and complete the table below to trace the algorithm using the data set:

20, 6, 38, 50, 40

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

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

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

The sorting algorithm could be part of a sub-program within a larger program.

Explain the benefits of using sub-programs when constructing a larger program.

Award [1] for any two from:

LIMIT;
MINIMUM;
COUNTER1;
COUNTER2;
TEMPORARY.

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.

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

Bubblesort;

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

Award [3 max].
Sub-programs contain reusable code (for use in other programs);
A large programming project can be divided into sub-programs;
Different sub-programs can be constructed by different programmers;
Future maintenance is easier due to the organisation of the large program (into sub-programs);

No real problems noted with this question other than a few candidates did not accurately copying the variable names as provided in the algorithm.

Many fully correct or partially correct responses to this question were seen, however, a significant number of candidates did not fully trace the algorithm to its conclusion, therefore limiting their mark for the question.

Most candidates attempted to construct this algorithm and the vast majority made use of pseudocode, rather than a programming language, unfortunately, very few achieved full marks. The usual reason was that candidates did not give a nested loop, which made the awarding of full marks difficult, as the outer loop also makes use of a flag as its terminal condition, therefore also affecting one of the other marking points. Many candidates incorrectly made use of the conditional IF statement as though it was a loop, thereby creating an ‘IF loop’.

Many candidates recognised that the algorithm was a sorting routine, but not all specified the correct type. Other candidates thought it was a search routine.

A number of versions of correctly operating responses were seen for this question, some of which were given in pseudocode, others were in programming code. However, a small number of responses were not given inside a loop, so therefore would only print one of the values.

Many responses seen were quite brief making it difficult to award all the marks, as the responses did not cover sufficient distinct marking points. However, the responses seen demonstrated that candidates understood the benefits of using sub-programs when constructing a larger program, and with a bit more detail in their answer, could have achieved full marks.