Lesson 8 of 8 · Functions and Arrays · 4 min read · Updated

Multi-dimensional arrays: sorting and searching

Three and more dimensions, finding a value in a table, and sorting rows or the whole table.

C allows any number of dimensions. int sales[2][3][4] could hold 2 years × 3 shops × 4 quarters = 24 values, and sales[1][0][3] is year 1, shop 0, quarter 3. Each extra dimension simply adds one more index and one more nested loop.

c
#include <stdio.h>

int main(void)
{
    int sales[2][3][4] = {0};          /* all 24 values start at 0 */
    sales[1][0][3] = 950;

    int count = sizeof(sales) / sizeof(sales[0][0][0]);
    printf("%d values, sales[1][0][3] = %d\n", count, sales[1][0][3]);
    return 0;
}
Output
24 values, sales[1][0][3] = 950

Searching a 2D array

c
#include <stdio.h>

int main(void)
{
    int a[3][4] = {{15, 8, 23, 4}, {42, 16, 9, 31}, {7, 12, 27, 3}};
    int key = 27, found = 0;

    for (int r = 0; r < 3 && !found; r++) {
        for (int c = 0; c < 4; c++) {
            if (a[r][c] == key) {
                printf("%d found at [%d][%d]\n", key, r, c);
                found = 1;
                break;
            }
        }
    }
    if (!found) {
        printf("%d not found\n", key);
    }
    return 0;
}
Output
27 found at [2][2]

The found flag does two jobs: the break leaves the inner loop, and && !found in the outer test stops the outer loop too. After the loops, the flag tells you whether to print "not found".

Sorting each row, then the whole table

c
#include <stdio.h>

#define ROWS 3
#define COLS 4

void print(int a[ROWS][COLS])
{
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            printf("%4d", a[r][c]);
        }
        printf("\n");
    }
}

int main(void)
{
    int a[ROWS][COLS] = {{15, 8, 23, 4}, {42, 16, 9, 31}, {7, 12, 27, 3}};

    /* 1. Bubble-sort every row on its own */
    for (int r = 0; r < ROWS; r++) {
        for (int i = 0; i < COLS - 1; i++) {
            for (int j = 0; j < COLS - 1 - i; j++) {
                if (a[r][j] > a[r][j + 1]) {
                    int t = a[r][j];
                    a[r][j] = a[r][j + 1];
                    a[r][j + 1] = t;
                }
            }
        }
    }
    printf("Each row sorted:\n");
    print(a);

    /* 2. Sort the whole table: number the cells 0..11 row by row */
    int n = ROWS * COLS;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            int r1 = j / COLS, c1 = j % COLS;
            int r2 = (j + 1) / COLS, c2 = (j + 1) % COLS;
            if (a[r1][c1] > a[r2][c2]) {
                int t = a[r1][c1];
                a[r1][c1] = a[r2][c2];
                a[r2][c2] = t;
            }
        }
    }
    printf("Whole table sorted:\n");
    print(a);
    return 0;
}
Output
Each row sorted:
   4   8  15  23
   9  16  31  42
   3   7  12  27
Whole table sorted:
   3   4   7   8
   9  12  15  16
  23  27  31  42

The trick for sorting the whole table: give every cell a single number k from 0 to 11, row by row. Cell k is at row k / COLS and column k % COLS. Then an ordinary one-dimensional bubble sort works on the table.

Note

#define ROWS 3 gives the size a name. Change it in one place and every loop and declaration follows — far safer than typing 3 in ten places.

In a table with 4 columns, cell number k = 9 (counting row by row from 0) is at which row and column?

Try this now

  1. Find the largest value in a 3 × 4 table and print its row and column.
  2. Sort each column of a table instead of each row.
  3. After sorting the whole table, search it with binary search, using k / COLS and k % COLS to reach each cell.

Create a free account to save your progress, or sign in.