Как решать задачи на сортировку в ЕГЭ по информатике
Сортировка — одна из ключевых тем в кодификаторе ЕГЭ по информатике. Задачи на сортировку встречаются как в первой части (задания на анализ алгоритмов), так и во второй (программирование). Важно не просто знать, как работает тот или иной метод, но и уметь применять его на практике, особенно на языке Python.
В этой статье мы разберём три основных подхода: пузырьковую сортировку, сортировку выбором и использование встроенных функций sorted() и .sort(). Для каждого метода приведены примеры задач уровня ЕГЭ с пошаговыми решениями. Также ответим на частые вопросы школьников и родителей.
Материал рассчитан на учеников 10-11 классов, которые готовятся к экзамену самостоятельно или с репетитором.
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.
Сортировка пузырьком: принцип и пример задачи
Сортировка пузырьком — простейший алгоритм, который часто спрашивают на ЕГЭ. Его суть: многократно проходим по массиву, сравнивая соседние элементы, и меняем их местами, если они стоят в неправильном порядке. После каждого прохода самый большой элемент «всплывает» в конец массива, как пузырёк.
Алгоритм завершается, когда за проход не было ни одной перестановки. В худшем случае требуется O(n^2) сравнений и обменов.
На ЕГЭ могут попросить посчитать количество перестановок или написать фрагмент кода, реализующий пузырёк.
Дан массив: [7, 2, 5, 3, 1]. Сколько перестановок выполнит сортировка пузырьком до полной сортировки?
Шаг 1: проход 1: (7,2)->(2,7), (7,5)->(5,7), (7,3)->(3,7), (7,1)->(1,7). Перестановки: 4. Массив: [2,5,3,1,7].
Шаг 2: проход 2: (2,5) нет, (5,3)->(3,5), (5,1)->(1,5). Перестановки: 2. Массив: [2,3,1,5,7].
Шаг 3: проход 3: (2,3) нет, (3,1)->(1,3). Перестановки: 1. Массив: [2,1,3,5,7].
Шаг 4: проход 4: (2,1)->(1,2). Перестановки: 1. Массив: [1,2,3,5,7].
Шаг 5: проход 5: перестановок нет, сортировка завершена. Итого перестановок: 4+2+1+1 = 8.
Ответ: 8 перестановок.
Сортировка выбором: как работает и где применяется
Сортировка выбором — ещё один классический алгоритм. На каждом шаге находим минимальный элемент в неотсортированной части массива и меняем его с первым элементом этой части. Таким образом, после i-го шага первые i элементов стоят на своих местах.
Алгоритм всегда делает O(n^2) сравнений, но количество обменов — не более n. На ЕГЭ часто встречаются задачи на подсчёт числа обменов или на пошаговое выполнение.
Отсортируйте массив [5, 3, 8, 1, 9] методом выбора, записывая состояние массива после каждого обмена.
Шаг 1: ищем минимум в [5,3,8,1,9] — это 1 (индекс 3). Меняем с первым: [1,3,8,5,9].
Шаг 2: минимум в [3,8,5,9] — 3 (индекс 1). Меняем с самим собой (обмена нет). Массив: [1,3,8,5,9].
Шаг 3: минимум в [8,5,9] — 5 (индекс 3). Меняем с 8: [1,3,5,8,9].
Шаг 4: минимум в [8,9] — 8 (индекс 3). Меняем с самим собой. Массив: [1,3,5,8,9].
Сортировка завершена. Количество обменов: 2.
Ответ: [1,3,5,8,9].
Использование sorted() и .sort() в Python: типовые задачи ЕГЭ
Встроенные функции Python — мощный инструмент, который часто упрощает решение задач. sorted() возвращает новый отсортированный список, а .sort() сортирует исходный список на месте. Обе функции используют Timsort (гибрид сортировки слиянием и вставками), работающий за O(n log n).
На ЕГЭ важно уметь:
- сортировать списки чисел и строк;
- использовать параметр key для сортировки по ключу (например, len, lambda);
- сортировать в обратном порядке (reverse=True);
- применять сортировку для решения задач на поиск минимума/максимума, медианы, частотного анализа.
Дан список чисел: [15, 3, 8, 22, 1]. Найдите медиану (средний элемент после сортировки). Если элементов чётное количество — среднее арифметическое двух центральных.
Шаг 1: сортируем список с помощью sorted(): sorted([15,3,8,22,1]) -> [1,3,8,15,22].
Шаг 2: длина списка 5 (нечётная). Медиана — элемент с индексом 2 (третий): 8.
Ответ: 8.
Пример для чётной длины: [4,2,7,1] -> sorted = [1,2,4,7] -> медиана (2+4)/2 = 3.
Отсортируйте список строк по длине в порядке возрастания. Если длины равны, сохраните исходный порядок. Список: ['apple', 'kiwi', 'banana', 'pear'].
Шаг 1: используем sorted() с параметром key=len. Так как сортировка устойчива, порядок равных элементов сохраняется.
Шаг 2: sorted(['apple','kiwi','banana','pear'], key=len) -> ['kiwi','pear','apple','banana'] (длины: 4,4,5,6).
Ответ: ['kiwi','pear','apple','banana'].
Сравнение алгоритмов: как выбрать подходящий для задачи ЕГЭ
На ЕГЭ не требуется реализовывать сложные алгоритмы вроде быстрой сортировки, но нужно понимать, какой метод эффективнее в конкретной ситуации.
- Пузырёк: прост для понимания, но медленный. Подходит для маленьких массивов (до 100 элементов) или когда нужно показать пошаговый процесс.
- Выбор: чуть быстрее пузырька по числу обменов, но столько же сравнений. Хорош, когда обмены дороги (например, большие объекты).
- Встроенные функции: оптимальны в реальном коде. На ЕГЭ их можно использовать в задачах второй части, если не требуется ручная реализация.
Важно: если в задаче явно сказано «реализуйте сортировку пузырьком», то использовать sorted() нельзя — алгоритм должен быть написан вручную. Если же задание просто «отсортируйте», то можно применять встроенные средства.
Часто задаваемые вопросы о сортировке в ЕГЭ
Собрали вопросы, которые чаще всего возникают у школьников при подготовке.
Частые вопросы
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.