Arrays
| English | Chinese | Pinyin |
|---|---|---|
| array | 数组 | shù zǔ |
| element | 元素 | yuán sù |
| index | 索引 | suǒ yǐn |
| lower bound | 下界 | xià jiè |
| upper bound | 上界 | shàng jiè |
| dimension | 维度 | wéi dù |
| nested loops | 嵌套循环 | qiàn tào xún huán |
| linear search | 线性查找 | xiàn xìng chá zhǎo |
| bubble sort | 冒泡排序 | mào pào pái xù |
Seat 14C
- A cinema has 300 seats. Its booking system does not have 300 variables called
Seat1A,Seat1B,Seat1C. It has one array 数组, and your ticket is an address into it: row 14, seat C. - One name, hundreds of values, each found by a number. Add a row and the code does not change; loop over the numbers and you have checked every seat.
- Almost every Paper 2 algorithm walks an array: searching it, summing it, sorting it, finding its largest value.
- This lesson is the vocabulary, the declarations, and the four algorithms the examiner asks for in pseudocode and in words.
The vocabulary
- An array is a data structure holding a fixed number of elements 元素 of the same data type under one identifier, each reached by an index 索引.
- The lower bound 下界 and upper bound 上界 are the first and last valid index. The number of elements is upper bound − lower bound + 1.
- The dimension 维度 is how many indices an element needs: one for a list, two for a table.
- In
ThisArray[n] ← 42the array has one dimension, the index is theINTEGERvariablen, and the element at that index receives42.
One identifier, an index for each element, bounds at both ends
An array stores:
An array is an ordered collection of same-type items accessed by index. (A record groups different types.)
An array is a data structure holding many values of the ______ type under one name.
Each value is reached by its index.
DECLARE Marks : ARRAY[0:99] OF INTEGER declares an array of ____ elements.
Upper bound minus lower bound plus one: 99 − 0 + 1 = 100. Both bounds are valid indices.
Worked example: declaring the array a task needs
- A declaration needs the identifier, the bounds and the data type.
- 120 readings that may have a decimal place:
DECLARE Data : ARRAY[1:120] OF REAL - A table of 150 rows and two columns of text:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Say the count if asked:
[0:99]holds 100 elements, not 99.
Which declaration holds a table of 150 rows and 2 columns of text?
Two dimensions, each with a lower and upper bound, and the element type. The second option is one long list; the third has no type; the fourth has no lower bounds.
Processing a 1-D array
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- A
FORloop from the lower bound to the upper bound visits every element once. - For a sum, count, maximum or minimum, set a running variable before the loop and update it inside.
2-D arrays
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- The first index is the row, the second the column. Nested loops 嵌套循环 visit every cell: the outer loop over rows, the inner over columns.
- Use 1-D for a single sequence and 2-D when the data has two natural dimensions, such as a grid of seats or a table of marks by student and subject.
Grid[row, column], always in that order
Index a 2-D array by [row, column]
A 2-D array is a grid. Grid[row, column] reaches exactly one cell — change the row and column to see which value you land on.
In Grid[2, 3], which cell is accessed?
The first index is the row, the second the column — so row 2, column 3.
Worked example: a linear search that can say "not found"
- A linear search 线性查找 checks each element in turn from the first until the target is found or the end is reached.
FoundAt ← -1
FOR i ← 1 TO n
IF A[i] = Target THEN
FoundAt ← i
ENDIF
NEXT i
IF FoundAt = -1 THEN
OUTPUT "Not found"
ELSE
OUTPUT "Found at ", FoundAt
ENDIF
-1can never be a valid index, so it means "not found". Initialise it before the loop and test it after. A search that never says "not found" loses a mark.
A linear search finds a value by:
A linear search examines elements one by one from the start until it finds the target (or reaches the end).
Setting FoundAt to -1 before a linear search lets the program report "not found" after the loop.
-1 is never a valid index, so if it is unchanged after the loop the target was not in the array.
Largest value, and where it is
Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
IF A[i] > Largest THEN
Largest ← A[i]
Position ← i
ENDIF
NEXT i
OUTPUT Largest, " at ", Position
- Start
Largestat the first element, never at 0: the array might be all negative. - The same shape counts or outputs the non-blank elements: compare each with the marker for unused,
""or-1, and count only those that differ.
Bubble sort
- A bubble sort 冒泡排序 makes repeated passes through the array comparing adjacent pairs and swapping those out of order, until a pass makes no swaps.
- After each pass the largest unsorted value has bubbled to the end, so the next pass can stop one place earlier.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Limit - 1
IF Data[Index] > Data[Index + 1] THEN
Temp ← Data[Index]
Data[Index] ← Data[Index + 1]
Data[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Limit ← Limit - 1
UNTIL Swapped = FALSE
Each pass carries the largest remaining value to the end
Put the steps of one bubble-sort pass, and its ending, in order.
Reset the flag, sweep and swap, shrink the limit, stop when a whole pass made no swap.
Worked example: where the bubble-sort marks are
- The outer loop that repeats until a pass makes no swaps; the
Swappedflag reset toFALSEat the start of each pass and setTRUEinside theIF. - The three-line swap through a temporary variable. Two lines lose a value.
- The shrinking limit, one less each pass, because the largest value has already reached the end.
- In words, for a stepwise-refinement question: repeat until sorted; on each pass compare adjacent pairs; swap any pair out of order; after each pass the largest unsorted value is at the end.
Which features earn marks in an efficient bubble sort? Select all that apply.
Flag, swap with a temporary, shrinking limit: those are the marks. Copying the array is not part of the algorithm.
Worked example: removing and inserting
- Remove an item: find its index with a linear search; move every later element one place towards the start so the gap closes; mark the last element as unused, or reduce the count.
- Insert into a sorted array: find the first index whose element is larger; move that element and every later one one place towards the end, starting from the last; store the new value in the gap.
- Move from the end when opening a gap and from the start when closing one, or you overwrite the value you are about to move.
An array holds many items of the SAME type reached by index, while a record groups fields of (possibly) DIFFERENT types reached by name.
A 2-D array suits a grid (rows × columns); a record suits one thing described by several named fields.
Marks that slip away
[0:99]holds 100 elements. Count both bounds.- An index is an
INTEGER; a declaration needs the type as well as the bounds. Grid[row, column]: row first. Swapping them reads the wrong cell in every nested loop.- A swap needs a temporary variable; a search needs a "not found" path; a bubble sort ends when a pass makes no swaps, not after a fixed number of passes.
You've got it
- an array holds a fixed number of same-type elements under one identifier, reached by an index between the lower and upper bound; count = upper − lower + 1
- 1-D is a list, 2-D is a table
[row, column]walked by nested loops; declare with bounds and type - linear search:
FoundAt ← -1, loop, store the index, test after the loop; largest value: start atA[1], keep the position - bubble sort: passes of adjacent compare-and-swap with a temporary, a
Swappedflag, a shrinking limit, until a pass makes no swaps