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

В разделе 5 сумма и среднее n чисел считались «на лету»: число прочитано, прибавлено и забыто. Но задача «вывести числа, которые больше среднего» так не решается: среднее известно только после ввода последнего числа, а сравнивать с ним нужно все числа. Значения приходится хранить. Заводить переменные x1, x2, … x100 бессмысленно — к ним не обратиться в цикле. Нужна одна переменная, которая хранит много значений, пронумерованных по порядку, — массив.

// Числа выше среднего: значения нужны дважды — их приходится хранить в массиве
#include <iostream>
#include <iomanip>
#include <limits>

constexpr int N = 100;                  // вместимость массива

bool readNumber(int low, int high, int& value);

int main()
{
    int n;
    std::cout << "How many numbers (1..100): ";
    if (!readNumber(1, N, n)) {
        return 1;
    }
    int a[N];
    long long sum = 0;
    std::cout << "Numbers (-1000..1000): ";
    for (int i = 0; i < n; ++i) {
        if (!readNumber(-1000, 1000, a[i])) {
            return 1;
        }
        sum += a[i];
    }

    const double average = static_cast<double>(sum) / n;
    std::cout << std::fixed << std::setprecision(2) << "Average: " << average << "\nAbove:";
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] > average) {
            std::cout << ' ' << a[i];
            ++count;
        }
    }
    std::cout << "\nCount: " << count << '\n';
    return 0;
}

// readNumber — из раздела 7, пункт 07

How many numbers (1..100): 5
Numbers (-1000..1000): 3 8 1 9 4
Average: 5.00
Above: 8 9
Count: 2

• int a[N]; — массив из N элементов типа int. Элементы — a[0], a[1], …, a[N - 1]; число в скобках — индекс, номер элемента, начиная с нуля.
• Элемент массива — обычная переменная типа int. Его можно передать в readNumber как параметр-ссылку int&: функция запишет прочитанное число прямо в a[i].
• Индекс — любое целое выражение: a[i], a[i + 1], a[n - 1]. Поэтому к массиву обращаются в цикле.

Размер массива — константа, известная при компиляции: число или constexpr (раздел 3). Компилятор отводит под массив память один раз, и размер не меняется. Запись int a[n];, где n введено с клавиатуры, g++ пропускает молча — это расширение GCC, а не C++: другие компиляторы её не собирают, а с ключом -pedantic g++ предупреждает:

warning: ISO C++ forbids variable length array 'a' [-Wvla]

Поэтому массив объявляется с запасом — вместимость N, — а сколько элементов заполнено, хранит отдельная переменная n. Работают только с a[0] … a[n - 1]; остальные N − n элементов не используются. При вводе n обязательно проверяется n <= N.

Массив нельзя присвоить целиком и нельзя сравнить целиком. b = a не собирается (invalid array assignment), а a == b сравнивает не элементы, а адреса массивов (раздел 9) и всегда ложно для двух разных массивов — g++ предупреждает: comparison between two arrays. Копирование и сравнение — поэлементно, циклом.

Почти любая обработка — цикл for (int i = 0; i < n; ++i) и один из алгоритмов раздела 5, только значения берутся не из ввода, а из массива:

// Наибольший элемент и его индекс — начальное значение из самого массива
int maxIndex = 0;
for (int i = 1; i < n; ++i) {
    if (a[i] > a[maxIndex]) {
        maxIndex = i;                   // строгое > — первое вхождение, >= — последнее
    }
}

// Поиск первого вхождения x: индекс или -1
int found = -1;
for (int i = 0; i < n && found == -1; ++i) {
    if (a[i] == x) {
        found = i;
    }
}

// Сравнение соседей: сколько раз элемент больше предыдущего
int rises = 0;
for (int i = 1; i < n; ++i) {          // с 1: у a[0] нет предыдущего
    if (a[i] > a[i - 1]) {
        ++rises;
    }
}

• Максимум начинается с элемента массива, а не с 0: у массива из отрицательных чисел «максимум 0» — ошибка. Хранить удобнее индекс — значение всегда a[maxIndex].
• −1 — признак «не найдено»: такого индекса не бывает. После цикла if (found == -1).
• Границы цикла подбираются под обращения внутри. Если в теле a[i - 1] — начинать с 1; если a[i + 1] — заканчивать на i < n - 1. Проверка: подставить первое и последнее значение i и убедиться, что все индексы в теле — от 0 до n - 1.

C++ не проверяет индекс. a[3] у массива int a[3] — это просто память сразу за последним элементом, и программа прочитает оттуда что-то или запишет туда. Там может оказаться другая переменная, служебные данные функции или чужая память — тогда Windows завершит программу. По стандарту это неопределённое поведение: результат зависит от компилятора, ключей и соседних строк кода.

int before = 1;
int a[3] = {0, 0, 0};
int after = 2;
for (int i = 0; i <= 3; ++i) {        // <= вместо <: четвёртая запись — мимо массива
    a[i] = 7;
}
std::cout << before << ' ' << after << '\n';

Такая программа может вывести 1 2 — и ошибка останется незамеченной, — а может 7 2 или 1 7: семёрка затёрла соседнюю переменную. Без оптимизации g++ обычно молчит; с -O2 иногда предупреждает, но рассчитывать на это нельзя. Проверка g++ 14 под Linux: без ключей программа молча печатает 1 7, а с -O2 печатает 1 2 и выдаёт предупреждения:

bounds.cpp:10:14: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
bounds.cpp:10:12: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds=]

Обмен двух элементов — через временную переменную, как swapRef в разделе 7. Реверс на месте — обмен пар с двух концов до середины: i идёт от 0, парный индекс — n - 1 - i, цикл — до i < n / 2 (иначе каждая пара поменяется дважды и массив вернётся к исходному).

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

// Удаление элемента по индексу: элементы правее сдвигаются на одну позицию влево
#include <iostream>

constexpr int N = 10;

int main()
{
    int a[N] = {10, 20, 30, 40, 50};
    int n = 5;                          // заполнено: a[0] .. a[n - 1]

    int k;
    std::cout << "Index to remove (0.." << n - 1 << "): ";
    std::cin >> k;
    if (std::cin.fail() || k < 0 || k >= n) {
        std::cout << "Error: no such index\n";
        return 1;
    }

    for (int i = k; i < n - 1; ++i) {
        a[i] = a[i + 1];
    }
    --n;

    for (int i = 0; i < n; ++i) {
        std::cout << a[i] << ' ';
    }
    std::cout << "\nn = " << n << '\n';
    return 0;
}

Index to remove (0..4): 1   ->  10 30 40 50 / n = 4
Index to remove (0..4): 4   ->  10 20 30 40 / n = 4
Index to remove (0..4): 5   ->  Error: no such index

Цикл сдвига — до i < n - 1, потому что в теле a[i + 1] (пункт 03). При k = n - 1 цикл не выполняется ни разу — удаляется последний элемент, достаточно --n. Старое значение a[4] физически остаётся в памяти, но после --n в обработку не попадает.

Вставка значения x на позицию k — зеркально: если n < N, элементы от конца до k сдвигаются на одну позицию вправо, и сдвиг идёт справа налево — иначе первый же сдвиг затрёт следующий элемент:

for (int i = n; i > k; --i) {           // n < N проверено: a[n] — свободное место
    a[i] = a[i - 1];
}
a[k] = x;
++n;

Удалить все элементы с некоторым свойством за один проход можно двумя индексами: i читает каждый элемент, kept — место для очередного оставляемого; if (оставить a[i]) { a[kept] = a[i]; ++kept; }, в конце n = kept. Удаление по одному в цикле тоже работает, но сдвигает хвост много раз и легко пропускает элемент, оказавшийся на месте удалённого.

int m[3][4]; — массив из 3 элементов, каждый из которых — массив из 4 int. Его удобно представлять таблицей — матрицей из 3 строк и 4 столбцов: m[i][j] — элемент строки i и столбца j, оба индекса с нуля. Инициализация — по строкам:

int m[3][4] = {
    {1, 2, 3, 4},
    {5, 6},                             // 5 6 0 0
    {}                                  // 0 0 0 0
};

В памяти строки лежат друг за другом: сначала 4 элемента строки 0, за ними строки 1 и так далее. Поэтому обход «строка за строкой» — внешний цикл по i, внутренний по j — идёт по памяти подряд. Как и у одномерного массива, вместимость задаётся константами, а фактические размеры rows и cols вводятся и проверяются:

// Матрица: ввод, вывод столбцами, суммы строк и столбцов
#include <iostream>
#include <iomanip>

constexpr int MAX_ROWS = 10;
constexpr int MAX_COLS = 10;

int main()
{
    int rows, cols;
    std::cout << "Rows and columns (1..10): ";
    std::cin >> rows >> cols;
    if (std::cin.fail() || rows < 1 || rows > MAX_ROWS || cols < 1 || cols > MAX_COLS) {
        std::cout << "Error: sizes must be 1..10\n";
        return 1;
    }

    int m[MAX_ROWS][MAX_COLS];
    std::cout << "Elements by rows:\n";
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            std::cin >> m[i][j];
        }
    }
    if (std::cin.fail()) {
        std::cout << "Error: not a number\n";
        return 1;
    }

    int colSum[MAX_COLS] = {};          // все нули
    for (int i = 0; i < rows; ++i) {
        int rowSum = 0;
        for (int j = 0; j < cols; ++j) {
            std::cout << std::setw(5) << m[i][j];
            rowSum += m[i][j];
            colSum[j] += m[i][j];
        }
        std::cout << " |" << std::setw(5) << rowSum << '\n';
    }
    for (int j = 0; j < cols; ++j) {
        std::cout << std::setw(5) << colSum[j];
    }
    std::cout << '\n';
    return 0;
}

Rows and columns (1..10): 2 3
Elements by rows:
1 2 3
4 5 6
    1    2    3 |    6
    4    5    6 |   15
    5    7    9

Сумма строки — одна переменная, которая обнуляется перед каждой строкой. Суммы столбцов копятся одновременно для всех столбцов — для них нужен массив colSum. std::setw(5) из <iomanip> выводит число в поле шириной 5 символов, и столбцы выравниваются.

Квадратная матрица n × n — отдельные понятия, которые встречаются в каждой второй задаче:

Сортировка — перестановка элементов так, чтобы они шли по возрастанию (или убыванию). Идея сортировки выбором: найти наименьший элемент и поставить его на место 0; из оставшихся найти наименьший и поставить на место 1; и так далее. После шага i элементы a[0] … a[i] — самые маленькие, по порядку, и больше не двигаются.

// Сортировка выбором по возрастанию; счётчики сравнений и обменов
#include <iostream>

constexpr int N = 100;

int main()
{
    int n;
    std::cout << "n (1..100): ";
    std::cin >> n;
    if (std::cin.fail() || n < 1 || n > N) {
        std::cout << "Error: n must be 1..100\n";
        return 1;
    }
    int a[N];
    std::cout << "Numbers: ";
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    if (std::cin.fail()) {
        std::cout << "Error: not a number\n";
        return 1;
    }

    int comparisons = 0;
    int swaps = 0;
    for (int i = 0; i < n - 1; ++i) {           // a[0..i-1] уже на своих местах
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            ++comparisons;
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            const int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
            ++swaps;
        }
    }

    std::cout << "Sorted:";
    for (int i = 0; i < n; ++i) {
        std::cout << ' ' << a[i];
    }
    std::cout << "\nComparisons: " << comparisons << ", swaps: " << swaps << '\n';
    return 0;
}

Трассировка для 5 2 8 1 9 3:

n (1..100): 6
Numbers: 5 2 8 1 9 3
Sorted: 1 2 3 5 8 9
Comparisons: 15, swaps: 3

Сравнений всегда 5 + 4 + 3 + 2 + 1 = 15, в общем случае n(n − 1)/2 — независимо от того, насколько массив был упорядочен: чтобы найти минимум, нужно просмотреть всех. Обменов — не больше n − 1. Для 100 элементов это 4950 сравнений — мгновенно; для миллиона — 5 · 10¹¹, часы работы. Для больших массивов есть быстрые методы (в стандартной библиотеке — std::sort), но в курсе сортировки пишутся руками: на них отрабатываются вложенные циклы и работа с индексами.

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

int comparisons = 0;
int swaps = 0;
bool swapped = true;
for (int pass = 1; pass < n && swapped; ++pass) {   // после прохода pass последние pass элементов на местах
    swapped = false;
    for (int j = 0; j < n - pass; ++j) {
        ++comparisons;
        if (a[j] > a[j + 1]) {
            const int temp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = temp;
            ++swaps;
            swapped = true;
        }
    }
}

n (1..100): 6
Numbers: 5 2 8 1 9 3
Sorted: 1 2 3 5 8 9
Comparisons: 14, swaps: 7

Устойчивость важна, когда сортируют по одному признаку то, что уже упорядочено по другому: строки матрицы, упорядоченные по первому столбцу, после устойчивой сортировки по сумме сохранят этот порядок среди строк с равной суммой. По убыванию — то же самое с обратным сравнением: a[j] < a[j + 1] у пузырька, поиск максимума у выбора.

Три типовые постановки — все сводятся к сортировке одномерного массива:

Сортировка строк по сумме — третья постановка. Сумма каждой строки считается один раз, до сортировки, и хранится в массиве rowSum; при обмене строк меняются и их суммы, иначе ключи перестанут соответствовать строкам:

// Фрагмент: строки по возрастанию сумм, выбором. Ввод и вывод — как в пункте 06
int rowSum[MAX_ROWS];                       // ключ сортировки — считается один раз
for (int i = 0; i < rows; ++i) {
    rowSum[i] = 0;
    for (int j = 0; j < cols; ++j) {
        rowSum[i] += m[i][j];
    }
}

for (int i = 0; i < rows - 1; ++i) {
    int minRow = i;
    for (int k = i + 1; k < rows; ++k) {
        if (rowSum[k] < rowSum[minRow]) {
            minRow = k;
        }
    }
    if (minRow != i) {
        for (int j = 0; j < cols; ++j) {    // обмен строк — поэлементно
            const int temp = m[i][j];
            m[i][j] = m[minRow][j];
            m[minRow][j] = temp;
        }
        const int temp = rowSum[i];         // и их сумм — ключ едет вместе со строкой
        rowSum[i] = rowSum[minRow];
        rowSum[minRow] = temp;
    }
}

Rows and columns (1..10): 3 3
Elements by rows:
3 3 3
1 0 0
2 2 1
    1    0    0 |    1
    2    2    1 |    5
    3    3    3 |    9

Выбор здесь лучше пузырька: обмен строк стоит cols присваиваний, а выбор делает не больше rows − 1 обменов. Полная программа — sortrows.cpp в примерах раздела; в практической работе №12 такая сортировка — по признаку вашего варианта.