Storing application data in arrays, lists and records, and the standard algorithms - linear search, binary search and a simple sort such as bubble sort.

What this dot point is asking

CCEA wants you to store an application's data in arrays, lists and records, and to apply the standard algorithms: linear search, binary search and a simple sort such as bubble sort. You must define a record (grouped fields of mixed types) and an array of records, describe each algorithm, state the requirement of binary search (sorted data) and the trade-offs between the approaches. Tracing or writing these algorithms, and choosing the right structure, are examined directly.

The answer

Arrays, lists and records

A record keeps all the data about one thing together, which is clearer and safer than several parallel arrays. An array (or list) of records is the natural store for an application's table of data loaded from a file.

Searching

Sorting with a bubble sort

A bubble sort orders a list by repeatedly passing through it, comparing each adjacent pair and swapping them if they are in the wrong order. Each pass moves the next-largest value to its correct end position; passes continue until a pass makes no swaps, meaning the list is sorted.

repeat
    swapped = false
    for i = 0 to length - 2
        if list[i] > list[i+1] then
            swap list[i] and list[i+1]
            swapped = true
        end if
    next i
until swapped = false

Bubble sort is simple but slow on large lists; it is the standard introductory sort CCEA expects you to describe and trace.

Worked example: tracing a binary search

Examples in context

Example 1. A contacts application. Each contact is a record with name, phone and email; the address book is an array of these records, loaded from a file at start-up. A linear search finds a contact by name in the unsorted list, and a bubble sort can order the array alphabetically so it displays tidily and, once sorted, a binary search can find a name quickly.

Example 2. A library catalogue. Thousands of book records are kept sorted by ISBN. A binary search locates a title in roughly a dozen comparisons rather than the thousands a linear search might need, showing why keeping data sorted pays off when lookups are frequent and the dataset is large.

Try this

Q1. State one requirement of a binary search that a linear search does not have. [1 mark]

• Cue. The list must already be sorted on the search key.

Q2. Define a record and give an example of the fields it might contain. [2 marks]

• Cue. A record groups related fields of possibly different types under one name, for example a Book record with title (string), year (integer) and available (Boolean).

Q3. State the condition that tells a bubble sort the list is fully sorted. [1 mark]

• Cue. A complete pass through the list makes no swaps.