Быстрая сортировка

Быстрая сортировка: идея алгоритма

Когда список чисел кажется слишком длинным, а простая сортировка начинает работать медленно, помогает быстрая сортировка. Её цель — упорядочить элементы, разделяя большую задачу на маленькие. Ты научишься выбирать опорный элемент, расставлять числа по сторонам и повторять процесс, чтобы уверенно решать задания по алгоритмам на уроках и экзаменах.

Быстрая сортировка, или quicksort, относится к алгоритмам «разделяй и властвуй». Сначала выбирается опорный элемент. Затем массив перестраивается так, чтобы слева оказались элементы, не превосходящие опорный, а справа — элементы не меньшие его. После этого левая и правая части сортируются отдельно.

Важно понимать: алгоритм не обязан сразу поставить опорный элемент на окончательное место при любом способе разбиения. Но после разбиения задача становится меньше, а это и даёт выигрыш во времени.

Если хочется сразу проверить понимание на коротких задачах, загляни в личный кабинет с бесплатной практикой: сначала реши самостоятельно, а затем сравни ход рассуждений.

Как работает разбиение

Рассмотрим массив и выберем опорным последний элемент. Два указателя помогают пройти по массиву. Первый показывает место, куда можно поставить следующий маленький элемент, второй последовательно проверяет значения. Если очередное число меньше или равно опорному, его меняют местами с элементом на позиции первого указателя.

После прохода опорный элемент меняется местами с первым элементом правой части. В результате он оказывается между двумя группами. Для учебного объяснения удобно использовать условие «меньше или равно слева, больше справа», хотя конкретная реализация может выбирать другое правило.

Массив: 7, 2, 9, 4, 3
Опорный элемент: 3
После разбиения: 2, 3, 9, 4, 7
Левая часть: 2
Правая часть: 9, 4, 7

Теперь алгоритм отдельно обрабатывает часть 2 и часть 9, 4, 7. Когда в подмассиве остаётся один элемент или ни одного, сортировать его уже не нужно.

Полный пример по шагам

Разберём массив 8, 3, 6, 1, 5. Возьмём последний элемент 5 в качестве опорного. Проходим слева направо: 8 больше 5, поэтому пока оставляем его справа. 3 меньше 5, значит, меняем местами 8 и 3. Массив становится 3, 8, 6, 1, 5.

Далее 6 больше 5 и остаётся на месте. Число 1 меньше 5: меняем его с 8. Получаем 3, 1, 6, 8, 5. После завершения прохода меняем опорный элемент 5 с первым элементом правой группы, то есть с 6.

Исходный массив: 8, 3, 6, 1, 5
После проверки 3: 3, 8, 6, 1, 5
После проверки 1: 3, 1, 6, 8, 5
Финальное разбиение: 3, 1, 5, 8, 6
Левая часть: 3, 1
Правая часть: 8, 6

Теперь сортируем 3, 1: опорный элемент 1, после разбиения получаем 1, 3. Для правой части 8, 6 опорным будет 6, поэтому результат — 6, 8. Объединяем готовые части вокруг 5: 1, 3, 5, 6, 8. Заметь: мы не склеиваем отдельные отсортированные списки сложным способом, а просто рассматриваем позиции внутри общего массива.

В рекурсивной записи функции базовый случай выглядит так: если левая граница больше или равна правой, вызов заканчивается.

Скорость и выбор опорного элемента

При удачном выборе опорного элемента массив каждый раз делится примерно пополам. Тогда средняя временная сложность быстрой сортировки равна O(n · log n), где n — количество элементов. Это заметно быстрее последовательного сравнения всех пар, для которого обычно получают O(n²).

Однако гарантии такого деления нет. Если массив уже отсортирован, а опорным постоянно становится крайний элемент, одна часть будет пустой, а другая уменьшится только на один элемент. В худшем случае сложность достигнет O(n²).

Ситуация	Поведение разделения	Оценка времени
Опорный близок к середине	Части примерно равны	O(n · log n)
Опорный крайний	Одна часть почти пустая	O(n²)
Один элемент	Разбиение не требуется	O(1)

Чтобы снизить риск плохого сценария, опорный элемент выбирают случайно, берут средний из нескольких значений или используют готовую библиотечную сортировку. На экзамене важно назвать среднюю и худшую оценки, если вопрос требует анализа сложности.

Для дополнительной тренировки алгоритмов можно открыть бесплатные задания в кабинете и отдельно потренировать чтение псевдокода.

Типичные ошибки в решении

Первая ошибка — перепутать направление сравнения. Если сортируем по возрастанию, элементы меньше или равны опорному должны попасть в левую часть, а большие — в правую. При сортировке по убыванию правило меняется.

Вторая ошибка — забыть обработать границы. Рекурсивные вызовы должны получать левую и правую границы именно подмассивов, а не всего массива. Иначе алгоритм будет снова сортировать уже готовые элементы или уйдёт в бесконечную рекурсию.

Третья ошибка — считать, что быстрая сортировка всегда быстрее любого другого метода. Её название связано со средней эффективностью, а не с безусловной гарантией. Также нужно уточнять, сортируется ли массив на месте. В распространённой реализации дополнительные массивы не создаются, но стек рекурсии всё равно занимает память.

Наконец, не смешивай quicksort с сортировкой слиянием. В быстрой сортировке главное действие — разбиение вокруг опорного элемента; в сортировке слиянием — объединение уже упорядоченных частей.

Что запомнить

Быстрая сортировка строится по схеме «выбрать опорный элемент → разделить массив → рекурсивно обработать части». Базовый случай — подмассив из нуля или одного элемента. При сбалансированных разбиениях средняя сложность составляет O(n · log n), но при неудачном выборе опорного элемента возможен случай O(n²).

На практике сначала внимательно выпиши исходный массив, опорный элемент и результат каждого обмена. Затем проверь, что все элементы слева подходят под условие сравнения, а справа — под противоположное. Такой контроль помогает заметить ошибку ещё до финального ответа.

Следующий шаг простой: зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. Начни с трассировки готового алгоритма, затем попробуй самостоятельно выполнить одно разбиение и объяснить, почему каждый обмен был нужен.