Arrays, from the beginning

1 · The problem arrays solve

Store the marks of five students with what you have so far and you write five variables: mark1, mark2, … mark5. Now find the highest. You need a separate if for every variable, because the name of each one is fixed when you write the program. A loop can't help. There's no way to say "the i-th variable" when the variables are mark1 to mark5.

Now make it 100 students. Or as many as the user types in. The copy-and-paste approach stops working, just as it did for "print Hello n times" before loops.

2 · Declaring one: a row of boxes

// data_type  name[size];
int    marks[5];          // room for 5 ints
double temperatures[7];   // room for 7 doubles
char   grades[10];        // room for 10 chars

The number in brackets is the size: how many values C reserves space for. marks[5] holds exactly five ints. Every element has the same type, so you can't mix ints and doubles in one array.

What C does with that declaration explains everything later on this page. It sets aside five boxes next to each other in memory, back to back with no gaps:

Two facts come straight out of the picture:

1. Numbering starts at 0. The first box is marks[0], the last is marks[4]. An array of size 5 has indices 0 to 4, and there is no index 5. The index says how many boxes to step past from the start: the first box is 0 steps in.
2. Any box can be reached instantly. The boxes are evenly spaced, so C finds box i with arithmetic (start + i × 4 bytes). It doesn't search for it. That's why marks[3] is just as fast as marks[0].

3 · Reading and writing one box

An element like marks[2] behaves exactly like an ordinary int variable. You can print it, use it in arithmetic, or assign to it:

printf("%d\n", marks[2]);   // 91
marks[2] = 95;              // overwrite that one box
printf("%d\n", marks[2]);   // 95

And here's the idea from §1 that makes arrays useful: the thing in the brackets can be any integer expression, including a variable:

int i = 3;
printf("%d\n", marks[i]);       // 68  — box 3
printf("%d\n", marks[i + 1]);   // 77  — box 4

Read marks[i] aloud as "marks, box i". Which box that is depends on what i holds right now. Put that inside a loop where i goes 0, 1, 2, 3, 4, and the same line of code visits every box. The rest of this lesson builds on that.

4 · Going past the end: C won't stop you

Ask for marks[5] and you might expect an error. There isn't one. C doesn't check array bounds. It does the same arithmetic as always (start + 5 × 4 bytes) and hands you whatever is stored there. That memory belongs to another variable, or to nothing at all.

int marks[5] = {72, 85, 91, 68, 77};
printf("%d\n", marks[5]);   // compiles, and runs

With clang -Wall you get a warning, because the 5 is written out explicitly:

warning: array index 5 is past the end of the array (that has type 'int[5]') [-Warray-bounds]

On the Mac these notes were written on, it then printed 1. That number means nothing, and yours may be different. What the C standard actually says is that going past the end is undefined behaviour: the program might print junk, might seem to work, or might crash. Writing past the end is the most dangerous case, because it overwrites someone else's data. The lecture's point that there's no compiler error is exactly right. Just don't count on a quiet wrong answer either: sometimes you get a crash.

5 · Giving the boxes starting values

A new array holds garbage, like a new int does (Lab 4's uninitialised-accumulator bug). You can fill it when you declare it:

int marks[5]   = {72, 85, 91, 68, 77};   // all five given
int numbers[]  = {10, 20, 30, 40};        // size left out: C counts 4
int zeros[100] = {0};                     // all 100 are 0
int part[5]    = {1, 2};                  // 1 2 0 0 0

The rule behind the last two lines: if you give fewer values than the size, the rest become 0. So {0} means "the first is 0, and the rest default to 0", which gives all zeros. Tested: part prints 1 2 0 0 0.

You can leave the size out only when you give values, because that's the only way C can count them. int numbers[]; on its own is an error:

error: definition of variable with array type needs an explicit size or an initializer

6 · The traversal pattern — the most important four lines

Putting §3 and Lab 4 together gives the pattern almost everything else uses:

for (int i = 0; i < size; i++) {
    // do something with array[i]
}

Check it against the loop questions from Lab 4. State: i starts at 0, the first index. Stop: keep going while i < size, so the last pass has i = size − 1, the last index. Advance: i++. The < is what makes it exact: for (i = a; i < b; i++) runs b − a times, and 5 − 0 = 5 boxes.

int marks[5] = {72, 85, 91, 68, 77};
for (int i = 0; i < 5; i++) {
    printf("%d\n", marks[i]);
}

72
85
91
68
77

Every other program on this page is this loop with a different line in the body. The lecture lists the four steps: declare, initialise, traverse, operate. The next three sections are three different "operate" lines.

7 · Sum and average

int sum = 0;                           // the total of the boxes seen so far: none yet
for (int i = 0; i < 5; i++) {
    sum += marks[i];
}
double average = (double) sum / 5;

sum = 393, average = 78.60

The accumulator is the one from Lab 4. What's new is where the numbers come from: the boxes, not i. That's why the body says marks[i], not i.

The (double) on the last line matters. sum and 5 are both ints, and int ÷ int drops the fraction. Without the cast, sum / 5 gives 78, and storing that in a double only makes it 78.00. Tested: without cast = 78.00. The cast turns sum into a double before dividing, so the division keeps the fraction.

8 · Minimum and maximum

int minVal = marks[0];             // first guess: the first box
for (int i = 1; i < 5; i++) {      // so start comparing from box 1
    if (marks[i] < minVal) {
        minVal = marks[i];         // found a smaller one — remember it
    }
}

Think of it as walking along the row holding the smallest number seen so far and swapping it whenever you meet a smaller one. Trace it: 72 (start) → 85 no → 91 no → 68 yes → 77 no. Result: min = 68. For the maximum, flip < to >. Tested: max = 91.

Why start with marks[0]? You need a starting guess, and it has to be one of the actual values. The first box always is. The obvious-looking alternative, starting at 0, fails:

9 · The sizeof trick — and where it stops working

Writing 5 into every loop is fragile. Change the array to 6 marks and you have to find every 5 and fix it. C can count for you:

int size = sizeof(marks) / sizeof(marks[0]);

sizeof(marks) = 20, sizeof(marks[0]) = 4, size = 5

sizeof gives a size in bytes. The whole array takes 20 bytes, and one element (an int on this machine) takes 4, so there are 20 ÷ 4 = 5 elements. Because it divides by the element size, it works for any element type.

10 · Linear search: is it in there?

To find where 91 is, check the boxes one by one from the left and stop at the first match. If you reach the end without one, it isn't there.

int target = 91;
int foundIndex = -1;                 // -1 means "not found (yet)"
for (int i = 0; i < 5; i++) {
    if (marks[i] == target) {
        foundIndex = i;
        break;                        // stop at the first match
    }
}

foundIndex = 2

Why −1? The answer is an index, and every index from 0 up is a real box. −1 can never be a valid index, so it clearly means "not found". Search for 80 and nothing ever overwrites it: tested, foundIndex for 80 = -1. After the loop, check if (foundIndex == -1) before using the result.

The break is Lab 4's "stop as soon as you find it". Without it the program still gives the right answer here, but keeps checking boxes 3 and 4 for nothing. With repeated values it would also give you the last match instead of the first.

11 · Binary search: faster, but only on sorted data

Linear search checks every box in the worst case. If the array is sorted, you can do much better, the way you'd look up a word in a dictionary. Open it in the middle, see which half the word must be in, and ignore the other half completely. Each look halves what's left.

int left = 0, right = n - 1;
int foundIndex = -1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)     { foundIndex = mid; break; }
    else if (arr[mid] < target) left = mid + 1;     // target is to the right
    else                        right = mid - 1;    // target is to the left
}

left and right mark the part of the array that could still contain the target. The loop keeps going while that part has at least one box (left <= right). Here's the lecture's trace, searching the sorted marks {68, 72, 77, 85, 91} for 85 (every row below is from the compiled program):

The lecture doesn't show what happens when the target isn't there. Search for 70:

This is how "not found" shows up: left and right cross. The + 1 and − 1 are what make them cross. Without them the range can stop shrinking and the loop never ends. It's the same guessing-game loop as Lab 4's Problem 5.

12 · Counting into categories

How many students got an A? A B? Instead of five separate counter variables, use an array of counters, one box per category:

int counts[5] = {0};   // counts[0]=A, [1]=B, [2]=C, [3]=D, [4]=F — all start at 0
for (int i = 0; i < 5; i++) {
    if      (marks[i] >= 90) counts[0]++;
    else if (marks[i] >= 80) counts[1]++;
    else if (marks[i] >= 70) counts[2]++;
    else if (marks[i] >= 60) counts[3]++;
    else                     counts[4]++;
}

A=1 B=1 C=2 D=1 F=0

Two arrays are working here: marks holds the data and counts holds the tallies. Note that counts is initialised with {0} for the same reason sum = 0 was in §7. The if … else if chain is Lab 3's grade ladder, unchanged.

13 · Sorting: putting the boxes in order

The lecture covers two methods. Both are loops inside loops (Lab 4 §7), and both only ever do two things: compare two boxes, and swap two boxes.

The swap, first

int temp = marks[i];      // 1. save one value
marks[i] = marks[i+1];    // 2. overwrite it
marks[i+1] = temp;        // 3. put the saved value in the other box

It takes three lines and a spare variable, like swapping the drinks in two full glasses: you need a third glass. Try it with two lines, b[0] = b[1]; b[1] = b[0];, and the first line destroys b[0] before you've saved it. Tested on {3, 9}: you get 9 9.

Bubble sort: fix neighbours that are out of order

Go along the row comparing each pair of neighbours, and swap any pair that's the wrong way round. After one full pass the largest value has "bubbled" to the end. It gets swapped along every time it meets something smaller. So the next pass can stop one box earlier. That's what 4 - pass in the lecture's code is for.

for (int pass = 0; pass < 4; pass++) {
    for (int i = 0; i < 4 - pass; i++) {
        if (marks[i] > marks[i+1]) {
            int temp = marks[i];  marks[i] = marks[i+1];  marks[i+1] = temp;
        }
    }
}

Selection sort: find the smallest, put it at the front

Use the min-index idea from §8's check: find the minimum of the whole array and swap it into box 0. Then find the minimum of boxes 1 to 4 and swap it into box 1, and so on. Each pass settles one more box at the front.

for (int i = 0; i < 4; i++) {
    int minIdx = i;
    for (int j = i + 1; j < 5; j++) {
        if (marks[j] < marks[minIdx]) minIdx = j;
    }
    int temp = marks[i];  marks[i] = marks[minIdx];  marks[minIdx] = temp;
}

Now watch both run on the lecture's marks. Step through each one and look at what gets compared:

What the stepper shows, and what the compiled program confirms:

The rows agree with the lecture's slides: both arrays are sorted after pass 3. Two details are worth knowing, because a trace question can ask about them:

• The code still runs pass 4. "Sorted after 3 passes" describes the data. The loop pass < 4 doesn't know that and runs a fourth pass anyway, making one comparison and no swaps.
• Selection sort's last pass swaps a box with itself. On pass 4 the minimum of {85, 91} is already at index 3, so the swap puts 85 back where it was. The data changes 3 times, but the swap code runs 4 times. That's the "exactly one swap per pass" on the slide.

Stopping early

If a whole pass of bubble sort makes no swaps, every neighbour pair is in order, so the array is sorted. A flag (Lab 4's pattern 5) can notice that and stop:

for (int pass = 0; pass < 4; pass++) {
    bool swapped = false;                 // #include <stdbool.h>
    for (int i = 0; i < 4 - pass; i++) {
        if (marks[i] > marks[i+1]) {
            int temp = marks[i];  marks[i] = marks[i+1];  marks[i+1] = temp;
            swapped = true;
        }
    }
    if (!swapped) break;                  // a clean pass: done
}

Be honest about what this buys. On the lecture's marks it still takes 4 passes (tested), because pass 3 made a swap, so it takes pass 4 to see a clean pass. Where it pays off is nearly sorted input. Given an array that's already sorted, it stops after 1 pass and 4 comparisons instead of 10 (tested). Labs often ask for this version.

14 · Two dimensions: rows and columns

A 2D array is a grid: an array of rows, where each row is itself an array. You need two indices, and the row always comes first.

int grid[3][4];   // 3 rows, 4 columns: 12 ints

Visiting every cell is a nested loop, the multiplication-table shape from Lab 4. The outer loop picks a row, and the inner loop walks along it:

int grid[2][3] = {{1, 2, 3}, {4, 5, 6}};   // one {…} per row
for (int r = 0; r < 2; r++) {
    for (int c = 0; c < 3; c++) {
        printf("%d ", grid[r][c]);
    }
    printf("\n");                          // end of a row
}

1 2 3 
4 5 6 

Adding two matrices, and flipping one

Addition works cell by cell. The same position in each grid goes into the same position in the answer: C[i][j] = A[i][j] + B[i][j];. Transpose turns rows into columns, so what was at row i, column j moves to row j, column i: T[j][i] = A[i][j];. The swapped indices are the whole idea. A 2×3 matrix becomes a 3×2 one, so T must be declared T[3][2].

int A[2][3] = {{1,2,3},{4,5,6}}, B[2][3] = {{10,20,30},{40,50,60}};
int C[2][3], T[3][2];
for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++) {
        C[i][j] = A[i][j] + B[i][j];
        T[j][i] = A[i][j];
    }

A+B:        transpose:
11 22 33    1 4
44 55 66    2 5
            3 6

Just a look: matrix multiplication

The lecture shows this only so you recognise its shape, and says it won't trace it. Each answer cell is a row of A times a column of B, multiplied pair by pair and added up. A (m×n) can only multiply B (n×p) when the middle numbers match, and the answer is m×p. The code needs three nested loops: two choose the cell, and the third adds up the products.

for (int i = 0; i < m; i++)
    for (int j = 0; j < p; j++) {
        R[i][j] = 0;                             // accumulator — reset per cell
        for (int k = 0; k < n; k++)
            R[i][j] += A[i][k] * B[k][j];
    }

More dimensions

int cube[2][3][4]; is 2 grids of 3 rows by 4 columns, 24 ints in total (tested). Each extra bracket is one more index and one more nested loop to visit everything. That's all the lecture asks you to know about it.

Where to go next

• Arrays notes: the patterns as cards, the class-statistics activity worked in full, the trap table, and the practice table. Keep this open during an open-book lab evaluation.
• Hanly & Koffman, chapter 7: declaring and subscripting arrays, sequential access with for, searching and sorting, multidimensional arrays. Check section numbers against your copy, and if the instructor names sections, go with theirs.