Раздел 8 — Массивы, поиск и сортировка

Массив — несколько значений одного типа, лежащих в памяти подряд, под одним именем. К элементу обращаются по индексу — номеру, который начинается с 0:

int marks[5] = {5, 4, 4, 3, 5};      /* 5 элементов: marks[0] … marks[4] */
marks[2] = 5;                        /* третий элемент */
int zeros[100] = {0};                 /* все 100 элементов — нули */
double prices[] = {9.5, 12.0, 7.25};   /* размер 3 — по числу значений */

  индекс     0     1     2     3     4
           ┌─────┬─────┬─────┬─────┬─────┐
  marks    │  5  │  4  │  5  │  3  │  5  │     5 × sizeof(int) = 20 байт подряд
           └─────┴─────┴─────┴─────┴─────┘

• Размер массива задаётся при объявлении константой и не меняется. Массив, размер которого известен только при работе программы, — динамический, это раздел 17.
• Число элементов массива — sizeof marks / sizeof marks[0]: размер в байтах, делённый на размер одного элемента. Работает только там, где массив объявлен, — в функции это уже не так (пункт 03).
• Массивы нельзя присваивать (a = b — ошибка) и сравнивать (a == b сравнивает адреса, а не элементы): копируют и сравнивают поэлементно, циклом.

Типичная программа: наибольшее число данных известно (например, до 100), фактическое число n вводится. Массив объявляется на наибольшее, используется первые n элементов:

/* n чисел: вывести в обратном порядке и найти, сколько из них больше среднего */
#include <stdio.h>
#include <stdlib.h>

enum { MAX_N = 100 };

int read_int(const char *prompt, int min, int max);   /* раздел 7, пункт 07 */

int main(void)
{
    int numbers[MAX_N];
    int n = read_int("n: ", 1, MAX_N);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        numbers[i] = read_int("", -1000000, 1000000);
        sum += numbers[i];
    }

    for (int i = n - 1; i >= 0; i--) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    double average = (double)sum / n;
    int above = 0;
    for (int i = 0; i < n; i++) {
        if (numbers[i] > average) {
            above++;
        }
    }
    printf("average %.2f, above %d\n", average, above);
    return 0;
}

n: 5            (числа по одному в строке: 3 8 1 9 4)
4 9 1 8 3
average 5.00, above 2

Без массива эту задачу не решить: среднее известно только после чтения всех чисел, а сравнивать с ним нужно каждое — числа приходится хранить.

Массив передаётся в функцию вместе с числом элементов — сама функция его не узнает:

void print_array(const int a[], int n)
{
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void fill_squares(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        a[i] = i * i;
    }
}
                    /* int sq[6]; fill_squares(sq, 6); print_array(sq, 6);  ->  0 1 4 9 16 25 */

Параметры передаются по значению (раздел 7), но массив целиком не копируется: в функцию передаётся адрес его первого элемента. Поэтому fill_squares меняет элементы массива вызывающего — в отличие от swap из раздела 7. Как это устроено, разбирается в разделе 10. Отсюда два правила:

• функция, которая только читает массив, объявляет параметр const int a[] — тогда случайная запись в него не соберётся, а по заголовку видно, что массив не изменится;
• sizeof a внутри функции даёт размер адреса (8 байт), а не массива; gcc предупреждает: 'sizeof' on array function parameter 'a' will return size of 'const int *'. Число элементов — всегда параметр.

Найти значение в массиве — перебрать элементы по порядку, пока не найдётся. Функция возвращает индекс найденного или −1:

/* Индекс первого элемента, равного key, или -1 */
int linear_search(const int a[], int n, int key)
{
    for (int i = 0; i < n; i++) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}

−1 — договорённость: индекса −1 не бывает, поэтому он означает «не найдено». Сравнений: в лучшем случае 1 (искомое — первое), в худшем n (последнее или его нет), в среднем при успешном поиске около n / 2. Линейный поиск работает с любым массивом, в том числе неупорядоченным.

Если массив упорядочен по возрастанию, можно сравнить ключ с серединой и отбросить половину, где его быть не может (раздел 2, пункт 07):

/* Индекс элемента, равного key, в упорядоченном массиве, или -1 */
int binary_search(const int a[], int n, int key)
{
    int low = 0, high = n - 1;           /* ключ, если есть, — в a[low..high] */
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) {
            return mid;
        }
        if (a[mid] < key) {
            low = mid + 1;                   /* ключ правее середины */
        } else {
            high = mid - 1;                  /* ключ левее */
        }
    }
    return -1;
}

Поиск 27 в массиве 3 7 11 15 19 23 27 31 35 39 (индексы 0–9):

Поиск 4: mid = 4 (19 > 4) → high = 3; mid = 1 (7 > 4) → high = 0; mid = 0 (3 < 4) → low = 1; low > high — не найдено за 3 шага.

• Инвариант — утверждение, верное перед каждой итерацией: «если ключ есть в массиве, он в a[low..high]». Каждая ветка его сохраняет, а отрезок сокращается хотя бы на 1 — поэтому цикл закончится, и ответ «не найдено» верен.
• mid = low + (high - low) / 2, а не (low + high) / 2: сумма двух больших индексов может переполнить int. Для массивов курса это не грозит, но привычка правильная.
• Шагов не больше ⌊log₂ n⌋ + 1: 10 элементов — 4, тысяча — 10, миллион — 20.
• Ошибки в границах — low = mid вместо mid + 1, low < high вместо <= — дают бесконечный цикл или пропуск элемента на краю. Проверяйте поиск первого, последнего, отсутствующего меньше всех и больше всех элементов и массива из одного элемента.

Точное число сравнений зависит от данных и деталей кода, но важнее, как оно растёт с размером n. Это записывают O-нотацией: O(f(n)) — «растёт не быстрее, чем f(n), с точностью до постоянного множителя». Постоянные множители и младшие слагаемые отбрасываются: n / 2 сравнений — это O(n), n(n − 1) / 2 — O(n²).

Компьютер выполняет порядка 10⁸–10⁹ простых операций в секунду. O(n²) при n = 10⁶ — 10¹² операций, это десятки минут; O(n log n) — доли секунды. Поэтому для больших данных выбор алгоритма важнее, чем скорость компьютера.

Найти наименьший элемент и поставить его на первое место, обменяв с тем, что там стоял; затем наименьший из оставшихся — на второе, и так далее:

void selection_sort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        int min_pos = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_pos]) {
                min_pos = j;
            }
        }
        if (min_pos != i) {
            int t = a[i];
            a[i] = a[min_pos];
            a[min_pos] = t;
        }
    }
}

Сравнений всегда (n − 1) + (n − 2) + … + 1 = n(n − 1) / 2 — здесь 15 — независимо от данных: даже упорядоченный массив сортируется так же долго. Обменов не больше n − 1 (здесь 3). Это O(n²) сравнений и O(n) обменов — выбор хорош, когда обмен дорог (большие записи).

Так сортируют карты в руке: левая часть массива уже упорядочена; очередной элемент вынимают и сдвигают вправо все бо́льшие его, пока не найдётся место:

void insertion_sort(int a[], int n)
{
    for (int i = 1; i < n; i++) {
        int current = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > current) {
            a[j + 1] = a[j];                  /* сдвиг вправо */
            j--;
        }
        a[j + 1] = current;
    }
}

Всего 10 сравнений и 7 сдвигов. Число сдвигов равно числу инверсий — пар элементов, стоящих не в том порядке: (5, 2), (5, 1), (5, 3), (2, 1), (8, 1), (8, 3), (9, 3). На упорядоченном массиве инверсий нет: n − 1 сравнений и ни одного сдвига — O(n). На упорядоченном по убыванию — n(n − 1) / 2, O(n²). Вставки быстры на «почти упорядоченных» данных — например, когда к упорядоченному списку добавили несколько записей.

Условие j >= 0 && a[j] > current держится на сокращённом вычислении (раздел 5): при j = -1 обращения к a[-1] не будет. Если переставить части условия, получится выход за границу.

Проходить по массиву, сравнивая соседей и меняя их местами, если они стоят не по порядку. После каждого прохода наибольший из неупорядоченных «всплывает» в конец. Если за проход не было ни одного обмена — массив упорядочен, можно остановиться:

void bubble_sort(int a[], int n)
{
    bool swapped = true;
    for (int pass = 0; pass < n - 1 && swapped; pass++) {
        swapped = false;
        for (int j = 0; j < n - 1 - pass; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swapped = true;
            }
        }
    }
}

Для 5 2 8 1 9 3: проход 1 → 2 5 1 8 3 9, проход 2 → 2 1 5 3 8 9, проход 3 → 1 2 3 5 8 9, проход 4 — обменов нет, остановка. Сравнений 5 + 4 + 3 + 2 = 14, обменов 7 — снова число инверсий: каждый обмен соседей устраняет ровно одну.

Устойчивая сортировка не меняет порядок равных элементов. Это важно, когда сортируют записи по одному полю: список студентов, упорядоченный по фамилии, после устойчивой сортировки по оценке остаётся упорядоченным по фамилии внутри каждой оценки. Выбор неустойчив: обмен на большое расстояние может перепрыгнуть через равный элемент.

Удалить элемент с индексом k — сдвинуть всё, что правее, на одну позицию влево и уменьшить n:

for (int i = k; i < n - 1; i++) {
    a[i] = a[i + 1];
}
n--;                                   /* 10 20 30 40, k = 1  ->  10 30 40 */

Вставить значение на место k — сдвинуть вправо, начиная с конца (иначе элементы затрут друг друга), если в массиве есть место:

for (int i = n; i > k; i--) {          /* требуется n < MAX_N */
    a[i] = a[i - 1];
}
a[k] = value;
n++;                                   /* 10 30 40, k = 1, value = 20  ->  10 20 30 40 */

Перевернуть массив — менять местами a[i] и a[n − 1 − i] для i от 0 до n / 2 − 1. Если дойти до n − 1, массив перевернётся дважды и вернётся к исходному.

Подсчитать частоты значений из небольшого диапазона — массив счётчиков, где индекс — значение:

int count[6] = {0};                    /* оценки 2..5 — индексы 2..5 */
for (int i = 0; i < n; i++) {
    count[marks[i]]++;                 /* marks[i] проверены: только 2..5 */
}

Один проход вместо сравнения каждой пары — O(n). Если вывести значения по счётчикам по порядку, получится упорядоченный массив: это сортировка подсчётом, O(n + k) для значений из k вариантов — быстрее любой сортировки сравнениями, но только для небольшого диапазона целых.