A-LevelComputer ScienceAlgorithm design and problem-solving9618/43 · May/June 2025 · Q220 Marks

A program sorts the data in the 1D array DataArray and searches DataArray for specific values. DataArray stores 14 integer values and is declared local to the main program.

(a)Write program code to create DataArray and initialise it with the following data values in the order they are written: 0 3 4 56 67 44 43 32 31 345 45 6 54 1[1]
(b)The function InsertionSort() takes an array of integers as a parameter. The function sorts the data in the array into ascending numerical order using an insertion sort. The function returns the sorted array. Write program code for InsertionSort() You must not use any inbuilt sorting functions for your programming language.[5]
(c)The procedure OutputArray() takes an array of integers as a parameter. The procedure outputs each element in the array from the first element to the last element. The output is on one line with a space between each number. An example output is: "0 3 4 56 67 44 43 32 31 345 45 6 54 1" Write program code for OutputArray()[2]
(d)(i)The main program needs extending to: • output the content of the unsorted array using OutputArray() • sort the array using InsertionSort() • output the content of the sorted array using OutputArray() Write program code to extend the main program.[2]
(d)(ii)Test your program. Take a screenshot of the output(s).[1]
(e)The function Search() performs a binary search to find ItemToFind in DataArray The function takes two parameters: • DataArray, an array of integers • ItemToFind, an integer to find in DataArray The function returns: • the index of ItemToFind if it is in DataArray • -1 if ItemToFind is not in DataArray Write program code for Search() You must not use any inbuilt searching functions for your programming language.[6]
(f)(i)The main program needs extending to call Search() with the sorted array four times: • the first time to find the index of the integer 0 • the second time to find the index of the integer 345 • the third time to find the index of the integer 67 • the fourth time to find the index of the integer 2 If the integer is found in the array, output an appropriate message that includes the index. If the integer is not found, output that it was not found. Write program code to extend the main program.[2]
(f)(ii)Test your program. Take a screenshot of the output(s).[1]

Mark scheme

Marking points from the official mark scheme (May/June 2025). The mark or mark type is shown in brackets.

2(a) 1 mark for array declared with data values: 0 3 4 56 67 44 43 32 31 345 45 6 54 1
[1 mark each] (b) • InsertionSort() header (and close) taking array as a parameter and returning (attempt at) sorted array • Looping through/for each element • Extracting element and comparing to sorted list ... • ...moving elements in sorted list • ...and inserting element in correct position (ascending order)
[1 mark each] (c) • OutputArray() header (and close) taking an array parameter and outputting the array contents ... • ...in correct format
2(d)(i) 1 mark each • Calling InsertionSort() with array parameter and storing/using return array • ...calling OutputArray() with array parameter before and after InsertionSort()
2(d)(ii) 1 mark for output showing unsorted then sorted array e.g. 0 3 4 56 67 44 43 32 31 345 45 6 54 1 0 1 3 4 6 31 32 43 44 45 54 56 67 345
[1 mark each] (e) • Search() header (and close) taking array and integer as parameters • Looping/recursive calls until no elements left/Low<=High and returning -1 if not found • ...calculating middle index and accessing this value • ...comparison of array at middle value to integer parameter • ...if they are equal return mid • ...if array[mid] < parameter update low to middle + 1, if array[mid] > parameter update high to middle – 1 // recursive call with updated low and updated high
[1 mark each] (f)(i) • Calling Search() with all four sets of values 0 345 67 2 • ...outputting 'not found' or index in appropriate message each time
2(f)(ii) 1 mark for output showing locations for first 3 and not found for 4th e.g. 0 found at index: 0 345 found at index: 13 67 found at index: 12 2 not found