Алгоритмы сортировки и их сложность: ЕГЭ по информатике

Тема охватывает основные алгоритмы сортировки (пузырьковая, вставками, выбором, быстрая, слиянием), их временную и пространственную сложность, а также умение анализировать и сравнивать алгоритмы по эффективности. На ЕГЭ по информатике требуется понимать принципы работы сортировок, оценивать их…

Что нужно знать

• Сортировка — упорядочивание элементов по возрастанию или убыванию.
• Простые сортировки (пузырьковая, вставками, выбором) имеют сложность O(n^2) в среднем и худшем случае.
• Быстрая сортировка (quicksort) в среднем O(n log n), в худшем O(n^2) (при неудачном выборе опорного элемента).
• Сортировка слиянием гарантирует O(n log n) в любом случае, но требует O(n) дополнительной памяти.
• Устойчивость сортировки: сохранение относительного порядка равных элементов (важно для сортировки по нескольким ключам).
• Сортировка подсчётом (counting sort) работает за O(n + k), где k — диапазон значений, но требует дополнительной памяти.

Термины и понятия

• Сортировка: процесс упорядочивания элементов массива по заданному критерию.
• Временная сложность: функция, описывающая зависимость числа операций от размера входных данных (обычно O-нотация).
• Пространственная сложность: объём дополнительной памяти, необходимый алгоритму.
• Устойчивая сортировка: сортировка, сохраняющая относительный порядок равных элементов.
• Пузырьковая сортировка: многократный проход по массиву с обменом соседних элементов, если они стоят в неправильном порядке.
• Сортировка вставками: построение отсортированной последовательности путём вставки каждого нового элемента в нужное место.
• Сортировка выбором: поиск минимального элемента в неотсортированной части и обмен с первым элементом этой части.
• Быстрая сортировка (quicksort): рекурсивный алгоритм, выбирающий опорный элемент и разделяющий массив на элементы меньше и больше опорного.

Частые ошибки

• Путают сложность быстрой сортировки: считают, что всегда O(n log n), забывая о худшем случае O(n^2).
• Не учитывают дополнительную память: например, сортировка слиянием требует O(n) памяти, а не O(1).
• Ошибочно считают сортировку выбором устойчивой (она неустойчива в стандартной реализации).
• Неправильно определяют количество операций в циклах: например, для пузырьковой сортировки внутренний цикл выполняется n-1, n-2, ... раз, что даёт n(n-1)/2 сравнений.

Как пройти тему

В курсе «Информатика» тема «Алгоритмы сортировки и их сложность» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Понятие алгоритма. Свойства алгоритмов. Способы записи
• Базовые алгоритмические конструкции: следование, ветвление, цикл
• Вспомогательные алгоритмы. Рекурсия
• Анализ алгоритмов. Определение результата работы алгоритма
• Поиск ошибок в алгоритмах. Отладка
• Обработка одномерных массивов: поиск, сортировка, статистика

← Предыдущая тема: Алгоритмы поиска кратчайших путей (Дейкстра, Флойд)
Следующая тема: Вычислительная сложность алгоритмов. Оценка O(f(n))

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