ЕГЭ по информатике: Сортировка и поиск

«Сортировка и поиск» — тема блока «Алгоритмы и программирование» кодификатора ФИПИ для ЕГЭ по информатике (КЕГЭ, 2026), охватывающая классические алгоритмы обработки массивов данных и оценку их эффективности. На экзамене сортировка и поиск нужны как инструменты в собственных программах (прежде всего задание 26), а понимание сложности — чтобы программа для заданий 25–27 работала за разумное время.

Материал охватывает полный цикл типовых задач: подсчёт количества сравнений и обменов при выполнении сортировки на конкретном небольшом массиве, определение промежуточного состояния массива после нескольких шагов сортировки вставками, трассировку бинарного поиска (число сравнений, найденный индекс) и сопоставление алгоритмов по классам сложности — O(n), O(n²), O(n log n), O(log n). Отдельный вопрос содержит реальный фрагмент кода на Python с вложенными циклами (классическая реализация пузырьковой сортировки), для которого нужно вычислить количество обменов.

Дистракторы построены на типичных заблуждениях школьников: путанице индексации с 0 или с 1, неверном подсчёте количества шагов при трассировке, смешении гарантированной сложности «в худшем случае» с усреднённой (например, быстрая сортировка в среднем работает за O(n log n), но в худшем случае деградирует до O(n²) — то же самое, что и у сортировки выбором).

Тема полезна выпускникам, готовящимся к ЕГЭ по информатике, а также студентам, начинающим системное изучение алгоритмов — понимание разницы между сложностью в худшем и в среднем случае необходимо для дальнейшего изучения структур данных. Флеш-карты закрепляют сложности основных алгоритмов сортировки, условие применимости бинарного поиска и саму нотацию O-большое.

• Трассировать пузырьковую сортировку, сортировку вставками и сортировку выбором на конкретном массиве
• Вычислять количество сравнений и обменов при выполнении алгоритмов сортировки
• Проводить трассировку бинарного поиска в отсортированном массиве
• Сравнивать временную сложность алгоритмов через нотацию O-большое: O(n), O(n²), O(n log n), O(log n)
• Различать гарантированную сложность алгоритма в худшем случае и усреднённую сложность

Материал основан на блоке кодификатора ФИПИ 2026 «Алгоритмы и программирование» (раздел «Сортировка и поиск») для ЕГЭ по информатике (КЕГЭ) — все 10 вопросов оригинальные, без воспроизведения реальных заданий из открытого банка ФИПИ.