Массив хранит много значений одного типа подряд в памяти. Сортировка упорядочивает их, а упорядоченный массив позволяет искать элемент двоичным поиском за log2(n) шагов.
Что нужно знать
- int a[N]; индексы 0…N − 1. Выход за границы C++ не проверяет — это ошибка программиста.
- Обход: for (int i = 0; i < n; i++) — сумма, подсчёт, максимум, как в Python.
- Матрица int m[R][C]: R · C элементов, строка за строкой; обход двумя вложенными циклами. Главная диагональ: i == j; выше — i < j; ниже — i > j; побочная: i + j == n − 1.
- Пузырёк — обмен соседей, после k-го прохода k наибольших на месте; вставки — элемент вставляется в отсортированную часть. Обе — n² в худшем случае.
- Слияние — делим пополам, сортируем, сливаем: всегда n·log n. Быстрая — разбиение по опорному: в среднем n·log n, в худшем n².
- Стандартная: sort(a, a + n); из <algorithm>.
- Двоичный поиск: только по ОТСОРТИРОВАННОМУ массиву; mid = (l + r) / 2, отбросить половину, где элемента быть не может. Шагов не больше ⌈log2(n + 1)⌉ — для 1000 элементов 10.
- Массив передают в функцию вместе с размером: void f(int a[], int n) — изменения элементов видны снаружи.
Где чаще всего ошибаются
- Обращаться к a[n] у массива из n элементов.
- Применять двоичный поиск к неупорядоченному массиву.
- Писать sort(a, a + n − 1) и терять последний элемент.
- Путать главную диагональ (i == j) с побочной (i + j == n − 1).
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Программирование на Python и C++ · 8 класс · C++: массивы, матрицы, сортировки и двоичный поиск