Arrays

Computer Science AS · Data types and structures. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science AS topics

The idea

An array stores many values of the same data type under one identifier. Each value is an element and its position is its index. The lowest index is the lower bound and the highest is the upper bound. A 1D array is a list. A 2D array is a table of rows and columns, so it needs two indexes.

A linear search checks each element in turn from the start, until the item is found or the end is reached. The data does not need to be sorted.

A bubble sort compares neighbouring pairs and swaps a pair that is in the wrong order. After each pass the largest value not yet placed has moved to its final position, so the next pass can be one comparison shorter.

Rules to remember

1D: DECLARE Marks : ARRAY[1:30] OF INTEGER. 2D: DECLARE Grid : ARRAY[1:3, 1:4] OF CHAR (row first, then column)
number of elements = upper bound − lower bound + 1, e.g. ARRAY[0:19] has 20 elements
Linear search of n items: 1 comparison at best, n comparisons if the item is last or not present
A swap needs a temporary variable:
Temp ← List[i]
List[i] ← List[i + 1]
List[i + 1] ← Temp
A bubble sort of n items needs at most n − 1 passes
A Boolean flag such as Swapped lets the sort stop early when a pass makes no swaps

Common mistake

Giving the fully sorted list as the result of the first pass. One pass only guarantees that the largest value is at the end, so follow the swaps pair by pair.

Worked example

An array holds 7, 3, 9, 2, 6. What is the order after the first pass of a bubble sort into ascending order?

Compare 7 and 3: wrong order, swap. The array is now 3, 7, 9, 2, 6.
Compare 7 and 9: correct order, no swap.
Compare 9 and 2: swap. The array is now 3, 7, 2, 9, 6.
Compare 9 and 6: swap. The array is now 3, 7, 2, 6, 9.

Answer: 3, 7, 2, 6, 9 (4 comparisons, 3 swaps, and 9 is now in its final place)

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Data types and records Files →Take a Computer Science AS test