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

Быстрая сортировка (англ. quicksort), часто называемая сортировкой Хоара, — это эффективный алгоритм сортировки, относящийся к классу алгоритмов «разделяй и властвуй». Разработанный в 1960 году британским информатиком Чарльзом Энтони Ричардом Хоаром, он является одним из самых широко используемых алгоритмов сортировки в вычислительной технике благодаря своей высокой производительности на практике. В среднем быстрая сортировка выполняет O(n log n) сравнений, что делает её значительно быстрее простых алгоритмов (например, пузырьковой сортировки) на больших массивах данных. Однако в худшем случае её сложность составляет O(n²), что является её основным недостатком.

¶История

Алгоритм быстрой сортировки был изобретён Ч. А. Р. Хоаром в 1960 году во время его работы над машинным переводом в Университете Кембриджа. Первоначально алгоритм был разработан для сортировки слов в русско-английском словаре. Хоар опубликовал описание алгоритма в 1961 году в статье «Algorithm 64: Quicksort» в журнале Communications of the ACM. Название «быстрая сортировка» (quicksort) было дано самим автором и отражает её ключевое преимущество — скорость работы на практике по сравнению с существовавшими на тот момент методами.

В последующие десятилетия алгоритм многократно анализировался и улучшался. Были предложены различные стратегии выбора опорного элемента (пивота), методы оптимизации для малых подмассивов (например, переход на сортировку вставками), а также модификации для работы со связанными списками и параллельными вычислениями. Алгоритм лёг в основу стандартной библиотечной функции qsort в языке C и является частью многих других стандартных библиотек.

¶Принцип работы

Быстрая сортировка основана на рекурсивном применении парадигмы «разделяй и властвуй». Основная идея заключается в выборе одного элемента массива, называемого опорным (pivot), и перераспределении остальных элементов таким образом, чтобы все элементы, меньшие опорного, оказались слева от него, а все большие — справа. Этот процесс называется разделением (partitioning). После этого алгоритм рекурсивно применяется к левой и правой частям массива.

¶Алгоритм разделения (схема Ломуто)

Существует несколько вариантов реализации процедуры разделения. Наиболее простая для понимания — схема Ломуто (Nico Lomuto). Она использует один индекс для прохода по массиву и второй для фиксации границы меньших элементов.

1. Выбирается опорный элемент (обычно последний элемент массива).
2. Устанавливается указатель i на начало массива (индекс первого элемента).
3. Для каждого элемента j от начала до предпоследнего:

• Если элемент arr[j] меньше или равен опорному, то элементы arr[i] и arr[j] меняются местами, и i увеличивается на 1.

1. По окончании цикла опорный элемент (последний) меняется местами с элементом arr[i]. Теперь опорный элемент находится на своей окончательной позиции, а все элементы слева от него меньше или равны ему, справа — больше.

¶Алгоритм разделения (схема Хоара)

Более эффективная и широко используемая — оригинальная схема Хоара. Она использует два указателя, движущихся навстречу друг другу.

1. Выбирается опорный элемент (часто средний элемент массива).
2. Устанавливаются два указателя: left на начало массива и right на конец.
3. Указатель left движется вправо, пока не найдёт элемент, больший или равный опорному.
4. Указатель right движется влево, пока не найдёт элемент, меньший или равный опорному.
5. Если left <= right, элементы на этих позициях меняются местами, указатели сдвигаются (left++ и right--).
6. Шаги 3-5 повторяются, пока left не станет больше right.
7. Рекурсия применяется к подмассивам от начала до right и от left до конца.

Схема Хоара выполняет в среднем в три раза меньше обменов, чем схема Ломуто, и считается стандартной реализацией.

¶Выбор опорного элемента

Выбор опорного элемента критически влияет на производительность алгоритма. Идеальный случай — когда опорный элемент делит массив на две равные (или почти равные) части.

• Первый или последний элемент: Простейший выбор, но крайне неудачный для уже отсортированных или почти отсортированных массивов. В этом случае разделение будет крайне несбалансированным (один подмассив будет содержать n-1 элемент, другой — 0), что приводит к худшей производительности O(n²).
• Средний элемент: Улучшенный вариант, который, однако, не гарантирует хорошего разделения для всех распределений данных.
• Случайный элемент: Выбор случайного элемента в качестве опорного значительно снижает вероятность наихудшего случая. Вероятность получить несбалансированное разделение при случайном выборе крайне мала.
• Медиана трёх: Выбор медианы из первого, среднего и последнего элементов массива. Этот метод обеспечивает хорошее приближение к медиане всего массива и является одним из наиболее популярных на практике. Он особенно эффективен для массивов, которые уже частично отсортированы.

¶Сложность алгоритма

• Лучший случай: O(n log n). Достигается, когда опорный элемент каждый раз делит массив на две равные части. Глубина рекурсии составляет log₂ n, на каждом уровне выполняется O(n) операций.
• Средний случай: O(n log n). Для случайных данных алгоритм демонстрирует эту асимптотическую сложность. Константа в O(n log n) у быстрой сортировки меньше, чем у многих других алгоритмов с такой же сложностью (например, у сортировки слиянием или пирамидальной сортировки), что и обеспечивает её практическую «быстроту».
• Худший случай: O(n²). Возникает, когда опорный элемент каждый раз оказывается минимальным или максимальным элементом подмассива. Это происходит, например, при использовании выбора первого элемента в качестве опорного на уже отсортированном массиве. В этом случае глубина рекурсии становится равной n, и на каждом уровне выполняется O(n) операций.

¶Оптимизации

Для повышения эффективности и предотвращения наихудших случаев применяются различные оптимизации:

• Сортировка вставками для малых подмассивов: Когда размер подмассива становится меньше определённого порога (например, 10-20 элементов), рекурсия прекращается, и для сортировки этого небольшого подмассива используется сортировка вставками. Сортировка вставками более эффективна для малых массивов, чем рекурсивный вызов быстрой сортировки.
• Introsort (интроспективная сортировка): Гибридный алгоритм, который начинается как быстрая сортировка, но переключается на пирамидальную сортировку, если глубина рекурсии превышает логарифмический порог. Это гарантирует сложность O(n log n) в худшем случае. Introsort является стандартным алгоритмом сортировки в стандартной библиотеке C++ (std::sort) и в некоторых реализациях Java.
• Трёхстороннее разделение (Dutch National Flag problem): Модификация, эффективно обрабатывающая массивы с большим количеством повторяющихся элементов. Массив делится на три части: элементы меньше опорного, равные опорному и больше опорного. Это позволяет не сортировать повторно равные элементы и значительно ускоряет работу на данных с множеством дубликатов.

¶Применение

Быстрая сортировка является одним из наиболее распространённых алгоритмов сортировки общего назначения. Она используется:

• В стандартных библиотеках языков программирования: Функция qsort в C, Array.Sort в .NET Framework (для примитивных типов), Arrays.sort в Java (для примитивных типов), sort в Python (использует Timsort, но для некоторых типов данных применяется быстрая сортировка).
• В операционных системах: Для сортировки файлов в каталогах, списков процессов и других внутренних структур данных.
• В базах данных: Для сортировки результатов запросов.
• В прикладном программном обеспечении: В электронных таблицах, текстовых редакторах, программах для работы с графикой и мультимедиа.

¶Критика и недостатки

Несмотря на свою популярность, быстрая сортировка имеет несколько недостатков:

• Неустойчивость (нестабильность): Быстрая сортировка не сохраняет относительный порядок равных элементов. Для задач, где стабильность важна (например, сортировка по нескольким ключам), используются другие алгоритмы (сортировка слиянием).
• Худшее время O(n²): Хотя вероятность наихудшего случая можно свести к минимуму, она не равна нулю. Для критически важных приложений, где время выполнения не должно превышать определённый лимит, могут применяться алгоритмы с гарантированной сложностью O(n log n), такие как пирамидальная сортировка или сортировка слиянием.
• Рекурсивная природа: Глубина рекурсии может быть значительной (в худшем случае O(n)), что может привести к переполнению стека вызовов для очень больших массивов. Итеративные реализации или оптимизация хвостовой рекурсии (сначала рекурсивно обрабатывать меньший подмассив) могут смягчить эту проблему.

¶Источники

1. Hoare, C. A. R. (1961). Algorithm 64: Quicksort. Communications of the ACM, 4(7), 321.
2. Sedgewick, R. (1978). Implementing Quicksort programs. Communications of the ACM, 21(10), 847-857.
3. Bentley, J. L., & McIlroy, M. D. (1993). Engineering a sort function. Software: Practice and Experience, 23(11), 1249-1265.
4. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). Вильямс.