Массивы: сортировка и поиск элементов — тренажёр для 9 класса

Раздел 1 — Определение

Массив — это упорядоченная структура данных фиксированной длины, элементы которой хранятся под общим именем и различаются целочисленным индексом. Индексация в большинстве школьных языков (Python, Паскаль с нулевой базой, C) начинается с 0, поэтому в массиве a из n элементов допустимы индексы от 0 до n − 1.

Сортировка — это перестановка элементов массива в порядке неубывания (или невозрастания) значений. Поиск — это определение индекса элемента с заданным значением либо установление факта его отсутствия. Две задачи связаны напрямую: быстрый двоичный поиск работает только на отсортированном массиве.

Раздел «Массивы: сортировка и поиск» завершает линию алгоритмики 9 класса: ученик переходит от записи алгоритма к оценке его вычислительной сложности — зависимости числа операций от размера данных n, записываемой в нотации «О большое».

Раздел 2 — Ключевые правила

Сортировка и поиск оцениваются числом сравнений элементов — именно эта операция считается основной при анализе эффективности.

1. Пузырьковая сортировка сравнивает соседние элементы a[j] и a[j+1] и меняет их местами при нарушении порядка. За один проход наибольший элемент «всплывает» в конец: из [5, 3, 8, 1] после первого прохода получается [3, 5, 1, 8].
2. Сортировка выбором на шаге i находит индекс минимума в неотсортированной части a[i..n−1] и один раз обменивает его с a[i]. Число обменов не превышает n − 1.
3. Обе сортировки выполняют n(n−1)/2 сравнений и имеют сложность O(n²): при n = 100 это 4950 сравнений, при n = 200 — уже 19 900, то есть рост вчетверо при удвоении данных.
4. Линейный поиск просматривает элементы подряд от начала; в худшем случае (элемента нет) он делает n сравнений — сложность O(n). Массив может быть неупорядоченным.
5. Двоичный поиск на каждом шаге сравнивает искомое значение x со средним элементом a[mid], где mid = (left + right) // 2, и отбрасывает половину отрезка. Число шагов не превышает ⌈log₂(n+1)⌉ — сложность O(log n). Обязательное условие — отсортированный массив.
6. Обмен двух элементов требует временной переменной: t = a[i]; a[i] = a[j]; a[j] = t.

Раздел 3 — Разбор примеров

Пример 1. Трассировка пузырьковой сортировки массива `[5, 3, 8, 1]`. Проход 1: (5,3) → обмен [3,5,8,1]; (5,8) → без обмена; (8,1) → обмен [3,5,1,8]. Проход 2: (3,5) — нет; (5,1) → обмен [3,1,5,8]. Проход 3: (3,1) → обмен [1,3,5,8]. Сравнений: 3 + 2 + 1 = 6 = 4·3/2. Каждый следующий проход короче предыдущего, потому что хвост массива уже отсортирован. Вывод: внешний цикл i от 0 до n−2, внутренний j от 0 до n−2−i.

Пример 2. Трассировка сортировки выбором массива `[7, 2, 9, 4]`. Шаг i=0: минимум 2 (индекс 1) → обмен с a[0] → [2,7,9,4]. Шаг i=1: минимум остатка [7,9,4] равен 4 (индекс 3) → обмен → [2,4,9,7]. Шаг i=2: минимум [9,7] равен 7 → обмен → [2,4,7,9]. Сравнений те же 6, но обменов только 3 против пяти у пузырька. Вывод: при «дорогом» перемещении данных выбором выгоднее.

Пример 3. Линейный поиск числа 9 в `[4, 7, 1, 9, 3]`. Сравнения: 4≠9, 7≠9, 1≠9, 9=9 → возвращается индекс 3 после четырёх сравнений. Поиск числа 6 потребует всех пяти сравнений и вернёт −1. Вывод: среднее число сравнений ≈ n/2, худшее = n, что и даёт O(n).

Пример 4. Двоичный поиск числа 66 в `[3, 7, 12, 18, 23, 29, 34, 41, 50, 66]`. left=0, right=9, mid=4: 23 < 66 → left=5. mid=7: 41 < 66 → left=8. mid=8: 50 < 66 → left=9. mid=9: 66 = 66 → индекс 9. Четыре сравнения вместо десяти, при этом ⌈log₂11⌉ = 4. Вывод: каждый шаг уменьшает зону поиска вдвое, поэтому рост n в 1000 раз добавляет лишь ≈10 шагов.

Раздел 4 — Таблица

Раздел 5 — Типичные ошибки

Двоичный поиск в неотсортированном массиве. Ученик применяет быстрый алгоритм к произвольным данным и получает −1 для присутствующего элемента. Неправильно: binary_search([4,7,1,9], 1) → −1. Правильно: сначала отсортировать массив, затем искать, либо использовать линейный поиск.

Выход за границу массива. Во внутреннем цикле пузырька пишут for j in range(n) и обращаются к a[j+1] при j = n−1. Правильно: for j in range(0, n−1−i) — верхняя граница уменьшается на уже отсортированный хвост.

Потеря значения при обмене. Запись a[i] = a[j]; a[j] = a[i] копирует одно значение дважды: массив [7,2] превращается в [2,2]. Правильно: ввести временную переменную t либо использовать a[i], a[j] = a[j], a[i].

Дробный индекс середины. Формула mid = (left + right) / 2 в Python даёт 4.5 и ошибку обращения по индексу. Правильно: целочисленное деление // (в Паскале — div).

Зацикливание двоичного поиска. Присваивание left = mid вместо left = mid + 1 оставляет отрезок неизменным, цикл while left <= right не завершается. Правильно: границы всегда сдвигаются за проверенный элемент: left = mid + 1 или right = mid − 1.

Раздел 6 — Пошаговый алгоритм

1. Определить задачу: упорядочить массив или найти элемент.
2. Проверить, отсортированы ли данные; при поиске в неупорядоченном массиве выбрать линейный поиск.
3. Записать границы циклов через n: внешний — 0 … n−2, внутренний в пузырьке — 0 … n−2−i.
4. Оформить обмен через временную переменную.
5. Выполнить трассировку на массиве из 4–5 элементов, записывая состояние массива после каждого прохода.
6. Подсчитать число сравнений и сопоставить с формулой: n(n−1)/2 для сортировок, n для линейного, ⌈log₂(n+1)⌉ для двоичного поиска.
7. Проверить результат: массив неубывающий (a[i] ≤ a[i+1] для всех i), найденный индекс удовлетворяет условию a[k] = x, а отсутствие элемента даёт −1.

Раздел 7 — Как запомнить

• «Пузырёк — соседи, выбор — минимум»: пузырьковая сортировка сравнивает пары рядом, выбором ищет наименьший во всём остатке.
• «Тяжёлый тонет, лёгкий всплывает» — за один проход пузырька крайний элемент занимает окончательное место.
• «Половина, ещё половина» — признак логарифма: 1024 → 512 → 256 → … → 1, ровно 10 делений.
• Формула-опора: 1 + 2 + … + (n−1) = n(n−1)/2 — число сравнений обеих квадратичных сортировок.
• Три условия двоичного поиска: сортировка, целое `mid`, сдвиг границы на ±1.