Как работает быстрая сортировка c

Быстрая сортировка и с чем её едят

Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.

Итак, быстрая сортировка, или, по названию функции в Си, Qsort — это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.

Алгоритм

Выбираем опорный элемент
Разбиваем массив на 3 части
- Создаём переменные l и r — индексы соответственно начала и конца рассматриваемого подмассива
- Увеличиваем l, пока l-й элемент меньше опорного
- Уменьшаем r, пока r-й элемент больше опорного
- Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
- Если l вдруг становится больше r, то прерываем цикл
Повторяем рекурсивно, пока не дойдём до массива из 1 элемента

// qsort (0, n-1);
* This source code was highlighted with Source Code Highlighter .

Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента — один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.

qsort

Выполняет быструю сортировку. Доступна более безопасная версия этой функции; см. раздел qsort_s .

Синтаксис

Параметры

base
Начало целевого массива.

number
Размер массива в элементах.

width
Размер элементов в байтах.

compare
Указатель на пользовательскую подпрограмму, которая сравнивает два элемента массива и возвращает значение, показывающее, как соотносятся их значения.

Remarks

Функция qsort реализует алгоритм быстрой сортировки для сортировки массива из number элементов, каждый из которых имеет размер width байт. Аргумент base является указателем на начало сортируемого массива. Функция qsort перезаписывает этот массив с использованием отсортированных элементов.

Во время сортировки функция qsort вызывает подпрограмму compare один или несколько раз и передает указатели на два элемента массива при каждом вызове. Если compare параметр указывает, что два элемента одинаковы, их порядок в результирующем отсортированном массиве не определен.

Подпрограмма сравнивает элементы и возвращает одно из следующих значений.

Сравнение возвращаемого значения функции	Описание
< 0	elem1 меньше elem2
0	elem1 эквивалентен elem2
> 0	elem1 больше elem2

Массив сортируется по возрастанию, как определено функцией сравнения. Для сортировки массива по убыванию измените смысл значений «больше» и «меньше» на противоположный в функции сравнения.

Эта функция проверяет свои параметры. Если compare параметр или number имеет значение NULL base NULL или имеет значение и number является ненулевым или width значение меньше нуля, вызывается обработчик недопустимых параметров, как описано в разделе Проверка параметров. Если выполнение может быть продолжено, функция возвращает управление и устанавливает для errno значение EINVAL .

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

Реализация быстрой сортировки на C/C++

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

Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем, и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++.

Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма.