Arrays

This book does not print what that program produced and will not. The values are not facts about any machine: the standard places no requirement on them, and a different compiler, a different optimisation level or a different day may give something else. The compiler's warning is the whole of what can honestly be shown.

What to do instead: check the index yourself where it could be wrong.

#include <stdio.h>

int at(const int *a, int n, int i, int fallback)
{
    if (i < 0 || i >= n) {
        printf("  index %d is outside 0 to %d\n", i, n - 1);
        return fallback;
    }
    return a[i];
}

int main(void)
{
    int a[3] = {10, 20, 30};

    printf("at(a, 3, 1)  = %d\n", at(a, 3, 1, -1));
    printf("at(a, 3, 5)  = %d\n", at(a, 3, 5, -1));
    printf("at(a, 3, -2) = %d\n", at(a, 3, -2, -1));
    return 0;
}

at(a, 3, 1)  = 20
  index 5 is outside 0 to 2
at(a, 3, 5)  = -1
  index -2 is outside 0 to 2
at(a, 3, -2) = -1

The practical: ten students

MU's Practical 5(a), roll numbers and names of ten students using an array. Names need an array of character arrays, which is the natural place to meet a two-dimensional array of char.

#include <stdio.h>

#define STUDENTS 5
#define NAME_LEN 20

int main(void)
{
    int roll[STUDENTS] = {101, 102, 103, 104, 105};
    char name[STUDENTS][NAME_LEN] = {"Anita Desai", "Rahul Mehta",
                                     "Fatima Shaikh", "Joseph D'Souza",
                                     "Priya Nair"};
    int marks[STUDENTS] = {63, 58, 72, 41, 89};

    printf("%-6s %-16s %6s\n", "Roll", "Name", "Marks");
    for (int i = 0; i < STUDENTS; i++) {
        printf("%-6d %-16s %6d\n", roll[i], name[i], marks[i]);
    }
    return 0;
}

Roll   Name              Marks
101    Anita Desai          63
102    Rahul Mehta          58
103    Fatima Shaikh        72
104    Joseph D'Souza       41
105    Priya Nair           89

MU asks for ten; five are shown so the output fits a page, and STUDENTS is the only thing to change. That is chapter 6's generality: the count is named in one place.

The four things you do to an array

These four patterns cover almost every array question on this paper, and each is worth knowing as a shape rather than as a program.

1. Total and average.

2. Largest and smallest. Start from the first element, not from zero. Starting from zero gives the wrong answer for an array of all-negative values, which is the classic trap.

3. Search. Chapter 30's found_at = -1 idiom.

4. Count how many satisfy something.

#include <stdio.h>

int main(void)
{
    int a[] = {-5, -17, -3, -42, -8};
    int n = (int) (sizeof a / sizeof a[0]);

    int total = 0;
    for (int i = 0; i < n; i++) {
        total += a[i];
    }

    int largest_wrong = 0;              /* the classic mistake */
    int largest = a[0];                 /* correct */
    int smallest = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > largest) { largest = a[i]; }
        if (a[i] < smallest) { smallest = a[i]; }
    }
    for (int i = 0; i < n; i++) {
        if (a[i] > largest_wrong) { largest_wrong = a[i]; }
    }

    int target = -3, found_at = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] == target) { found_at = i; break; }
    }

    int below = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < -10) { below++; }
    }

    printf("total %d, average %.2f\n", total, (double) total / n);
    printf("largest %d (starting from 0 would have said %d)\n",
           largest, largest_wrong);
    printf("smallest %d\n", smallest);
    printf("%d found at index %d\n", target, found_at);
    printf("%d value(s) below -10\n", below);
    return 0;
}

total -75, average -15.00
largest -3 (starting from 0 would have said 0)
smallest -42
-3 found at index 2
2 value(s) below -10

largest_wrong is 0, and 0 is not in the array. That is what starting a maximum at zero does. Start at a[0] and loop from 1.

The practical: sorting

MU's Practical 5(b), sorting into ascending or descending order. Bubble sort is the one to know: compare each adjacent pair and swap them if they are the wrong way round, and repeat until a pass makes no swap.

#include <stdio.h>

void print_array(const char *label, const int *a, int n)
{
    printf("%-12s", label);
    for (int i = 0; i < n; i++) {
        printf("%5d", a[i]);
    }
    printf("\n");
}

void bubble_sort(int *a, int n, int ascending)
{
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int i = 0; i < n - 1 - pass; i++) {
            int wrong_way = ascending ? a[i] > a[i + 1] : a[i] < a[i + 1];
            if (wrong_way) {
                int t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                swapped = 1;
            }
        }
        printf("  after pass %d: ", pass + 1);
        for (int i = 0; i < n; i++) {
            printf("%5d", a[i]);
        }
        printf("\n");
        if (!swapped) {
            printf("  no swap in that pass, so it is sorted\n");
            break;
        }
    }
}

int main(void)
{
    int a[] = {42, 8, 17, 4, 23, 15};
    int n = (int) (sizeof a / sizeof a[0]);
    int b[6];

    for (int i = 0; i < n; i++) { b[i] = a[i]; }

    print_array("original", a, n);
    printf("ascending:\n");
    bubble_sort(a, n, 1);
    print_array("sorted", a, n);

    printf("descending:\n");
    bubble_sort(b, n, 0);
    print_array("sorted", b, n);
    return 0;
}

original       42    8   17    4   23   15
ascending:
  after pass 1:     8   17    4   23   15   42
  after pass 2:     8    4   17   15   23   42
  after pass 3:     4    8   15   17   23   42
  after pass 4:     4    8   15   17   23   42
  no swap in that pass, so it is sorted
sorted          4    8   15   17   23   42
descending:
  after pass 1:    42   17    8   23   15    4
  after pass 2:    42   17   23   15    8    4
  after pass 3:    42   23   17   15    8    4
  after pass 4:    42   23   17   15    8    4
  no swap in that pass, so it is sorted
sorted         42   23   17   15    8    4

Three details that earn marks.

1. n - 1 - pass. After pass 1 the largest value is at the end, after pass 2 the two largest are, and so on. There is no point comparing them again.

2. The swapped flag. A pass with no swap means the array is in order, so the rest of the passes can be skipped. Without it, the loop always does n - 1 passes.

3. One function, both orders. The ascending parameter chooses the comparison. Writing two nearly identical functions is what chapter 6 called a failure of simplicity.

An array parameter is written int *a here, and int a[] means exactly the same thing in a parameter list. Chapter 41 explains why, and it is also why bubble_sort can change the caller's array while chapter 33's swap could not change two ints.

What this does NOT mean

An array is not a variable that holds many values. It is many objects with one name, and the name is not itself a value you can assign.

You cannot copy an array with =. b = a; does not compile. Copy element by element, or with memcpy.

You cannot compare arrays with ==. That compares addresses.

The size is not part of what a function receives. Pass it as a separate parameter. sizeof inside the function gives the size of a pointer.

An array's size must be known when it is declared, and cannot change afterwards. C99 allows a size from a variable, a variable-length array, which is a different thing and not for a first program.

a[n] is not the last element. a[n - 1] is.

An uninitialised array does not hold zeros. Only one with a partial initialiser does, and a static or global one.

Quick revision

• An array is a fixed number of same-type objects in consecutive memory.
• Indexes run 0 to n - 1. Loop with i < n, never i <= n.
• sizeof a / sizeof a[0] gives the count, where the array itself is in scope.
• No bounds checking. Out of range is undefined behaviour, not an error.
• Start a maximum or minimum at a[0] and loop from 1, never at 0.
• Search idiom: found_at = -1, set and break on a match.
• Cannot be copied with = or compared with ==.
• A function receives the address, so it can change the caller's array, and must be told the size.
• Bubble sort: adjacent compares, n - 1 - pass inner limit, and a swapped flag to stop early.

Test yourself

1. For int a[10];, what are the valid indexes?

0 to 9. a[10] is past the end.

2. How do you find the number of elements of an array?

sizeof a / sizeof a[0], provided the array itself is in scope rather than a parameter that received it.

3. What is wrong with int max = 0; before a loop looking for the largest element?

If every element is negative, the answer comes out as 0, which is not in the array. Start with max = a[0] and loop from index 1.

4. What happens when you read a[100] of a ten-element array?

Undefined behaviour. It may print a meaningless value, corrupt another variable or crash, and it is not an error the language reports.

5. Why can you not write b = a; to copy an array?

An array name is not a modifiable value. Copy element by element, or use memcpy.

6. In bubble sort, why is the inner loop bounded by n - 1 - pass?

Because each pass moves the largest remaining value to its final place at the end, so those positions need not be compared again.

7. How many passes does bubble sort need on an already sorted array with the swapped flag?

One. The first pass makes no swap, so the flag ends the loop.

What can be asked on this, and how to answer it

"What is an array? Explain its declaration and initialisation with examples." Define it, give the three declaration forms, state that indexes run from 0 to n - 1, and give the initialisation rules from chapter 21, including that omitted elements are zero. Add that there is no bounds checking, because that is the fact with consequences.

"Write a program to find the largest and smallest element of an array." Give the program with largest = a[0] and the loop from 1, and say in one line why starting at 0 is wrong. That sentence is worth a mark on its own.

"Write a program to sort an array in ascending order." Give bubble sort with the n - 1 - pass bound and the swapped flag, and show the array after each pass, which is what an examiner asks you to trace.

"Write a program to store and display the roll numbers and names of ten students." Give this chapter's program: an int array for the roll numbers and a two-dimensional char array for the names, printed in a loop with a formatted header.

"What is meant by array out of bounds? What does C do about it?" Using an index outside 0 to n - 1. C does nothing: there is no check, and the behaviour is undefined. The program may print rubbish, damage other data or crash, and checking is the programmer's responsibility.