Construct a pseudocode algorithm that will store the surnames in one array and first names in another.

Construct a pseudocode algorithm that will sort the surnames into alphabetical order using the bubble sort method. The order of the first names must also be changed so that they keep the same index as their corresponding surname.

Describe the process a binary search would follow to find a record in the surname array.

Outline one benefit of using sub-programmes to implement your algorithms from parts (a) and (b).

Award [4 max] 
Collection method NAMES.getNext() / NAMES.getData() correctly used;
Correct loop;
Correct use of index (in both arrays);
Correct assignment in array for surnames;
Correct assignment in array for first names;

Note:
Award 1 mark in case that string methods are used to separate ‘name’ and ‘surname’ in the data item.

Example answer 1:

NAMES.resetNext() // reset and
SURNAME[600] //initialization of arrays
FIRSTNAME[600] //may not appear in candidates’ responses
COUNTER = 0
loop while NAMES.hasNext()
    SURNAME[COUNTER] = NAMES.getNext()
    FIRSTNAME[COUNTER] = NAMES.getNext()
COUNTER = COUNTER + 1
end loop

Example answer 2

NAMES.resetNext()
loop COUNTER from 0 to 599
    SURNAME[COUNTER] = NAMES.getNext()
    FIRSTNAME[COUNTER] = NAMES.getNext()
end loop

Example answer 3 (assumes that items in the collection are objects- two attributes: surname and first name)

I = 0
loop while NAMES.hasNext()
        X= NAMES.getData()
        SURNAME[I] = X.surname
        FIRSTNAME[I] = X.firstname
        I = I + 1
end loop

Award [5 max] 
Correct outer loop;
Correct inner loop;
Checking of surname order;
Swapping surnames if necessary;
Swapping corresponding names;
Correct use of flag;

Example 1:

loop I from 0 to 599
   loop C from 0 to 598-I //accept 598
       if SURNAME[C] > SURNAME[C + 1] then
         TEMP1 = SURNAME[C]
         TEMP2 = FIRSTNAME[C]
         SURNAME[C] = SURNAME[C + 1]
         FIRSTNAME[C] = FIRSTNAME[C + 1]
         SURNAME[C + 1] = TEMP1
         FIRSTNAME[C + 1] = TEMP2
       end if
    end loop
end loop

Example 2:

FLAG = TRUE
loop while FLAG = TRUE
    FLAG = FALSE
    loop COUNTER from 0 to 598
       if SURNAME[COUNTER] > SURNAME[COUNTER + 1] then
         TEMP1 = SURNAME[COUNTER]
         TEMP2 = FIRSTNAME[COUNTER]
         SURNAME[COUNTER] = SURNAME[COUNTER + 1]
         FIRSTNAME[COUNTER] = FIRSTNAME[COUNTER + 1]
         SURNAME[COUNTER + 1] = TEMP1
         FIRSTNAME[COUNTER + 1] = TEMP2
         FLAG = TRUE
       end if
    end loop
end loop

Award [4 max] 

Example 1:
Calculate the index of the middle point in the array SURNAME: (first + last)/2;
Compare surname found with the one stored at middle point;
If greater than the value at the middle point, search the upper half of the array (right side) by calling the binary search method again with a new first index (first = middle + 1);
If smaller than the value at the middle point, search the lower half of the array (left side) by calling the binary search method with a new last (last = middle −1);
if found algorithm terminates;

Example 2:
Find the centre point of the array SURNAME[ ];
Compare surname to be found with the current name in SURNAME[ ];
If correct surname found => STOP;
Else if surname to be found is greater than the current name in SURNAME[ ]eliminate lower half of array from search and repeat algorithm;
Else if surname to be found is less than the name in SURNAME[ ] eliminate upper half of array from search and repeat algorithm;

Note: Allow a mark for provision for name not found;

Award [4 max] 

1 mark for a benefit (such as reusability, modularity, maintainability, readability)
1 mark for an expansion.

Example answer:
These sub-programs (sorting/searching) could be used in (many) other programs;
Which saves programmer’s time/ effort;

Candidates who realised that the data from the collection was to be accessed sequentially with the first item stored in one of two arrays, the second item in the second array, the third item in the first array, and so on, until the collection was empty, scored high marks for this question. Some candidates did not correctly apply standard collection methods so lost marks.

Candidates who scored highly in part a. also scored highly for this part. However, this question did see the full range of possible marks awarded. Candidates who were unable to complete the whole algorithm correctly generally achieved some of the marks, typically for performing correct swaps during the sort, or for correctly initialising and implementing one or both of the loops.

This question required a description for the binary search algorithm and was generally well answered with a high proportion of candidates achieving full marks. A small number of candidates incorrectly described a sorting algorithm, while others incorrectly described a linear search.

Most candidates achieved at least one of the marks for this question, with many acquiring both marks. Candidates most frequently recognised that the sub-programs could be re-used in other programs, therefore saving programming time.