Алгоритмы сортировки — это фундамент информатики. Среди них особое место занимает быстрая сортировка (QuickSort), разработанная Тони Хоаром. В этой статье мы подробно разберем, как она работает, почему носит звание «быстрой», а также выясним, почему на практике её поведение может сильно отличаться от симуляций, и при чем тут повторяющиеся элементы.
Суть алгоритма: «Разделяй и властвуй»
Быстрая сортировка, это алгоритм типа «разделяй и властвуй» для сортировки массива, основанный на процедуре разбиения. Его ключевым элементом является алгоритм переупорядочения. Вся логика строится вокруг выбора так называемого опорного элемента (pivot).
Как происходит процесс:
- Выбор опорного элемента: При каждом действии из массива выбирается опорный элемент.
- Разбиение (Partition): Прочие значения из массива сопоставляются с опорным. Меньшие помещаются слева от него, а большие или равные — справа;
- Рекурсия: Чтобы закончить сортировку, мы должны рекурсивно повторить упорядочивание для левой и правой половин массива, полученных после разбиения. Внутри полученных групп указывается новый опорный элемент, по которому повторно выполняется сортировка.
Почему она «быстрая»? Оценка сложности
Название алгоритма не случайно. Что касается сложности быстрой сортировки, то в лучшем и среднем случаях мы получаем сложность Ω(n log n); Это достигается за счет того, что при каждом разбиении массив делится примерно пополам, и глубина рекурсии составляет логарифм от числа элементов.
Однако в худшем случае сложность возрастает до O(n2). Когда это происходит? Если опорный элемент выбирается неудачно (например, это всегда минимальный или максимальный элемент), то далее сортировка списка длиной (n-1) опять даст подсписки из 0 и (n-2) элементов, и т.д.. Вместо деления пополам мы просто отсекаем по одному элементу за проход, что превращает алгоритм в медленную сортировку пузырьком.
Проблема повторяющихся элементов
В данном контексте важно разобрать, почему стандартная реализация быстрой сортировки может работать медленно на массивах с повторяющимися элементами (что отчасти перекликается с вашим запросом о «повторной рассорке»).
Если в массиве много одинаковых значений, классический алгоритм разбиения Хоара начинает создавать глубокие несбалансированные деревья рекурсии. Поскольку элементы, равные опорному, могут распределяться неравномерно (например, все уходят вправо), массив делится на подмассивы размером 1 и (n-1), что и ведет к деградации до O(n2).
Для решения этой проблемы была разработана трехпутевая быстрая сортировка (Dutch National Flag), которая делит массив не на две части (меньше и больше), а на три: меньше опорного, равные опорному и больше опорного. Это позволяет «выбрасывать» все дубликаты из дальнейшей рекурсии за один проход!
Парадокс производительности: Симулятор против Реального железа
Один из самых интересных аспектов быстрой сортировки — это её поведение на реальном оборудовании по сравнению с программными симуляторами (например, Valgrind).
В Valgrind новый, более сложный алгоритм (например, трехпутевое разбиение) на самом деле может оказаться медленнее, чем классическая AF-сортировка. В этом есть смысл: Valgrind — это просто симулятор процессора, поэтому алгоритм, который выполняет больше инструкций, имеет немного больше промахов в кеше и немного больше неверных предсказаний ветвлений, будет работать медленнее.
Но почему же он быстрее работает на реальном оборудовании? Современные процессоры обладают мощными конвейерами и предсказателями ветвлений. На реальном железе дополнительные инструкции окупаются тем, что алгоритм лучше адаптируется к данным (особенно с дубликатами), избегая катастрофического падения до O(n2) и предотвращая переполнение стека рекурсии. Процессор способен эффективно распараллеливать выполнение инструкций, нивелируя накладные расходы.
Дополнительные преимущества QuickSort
- Распараллеливание: Быструю сортировку легко распараллелить и разбить на отдельные процессы. Левую и правую части массива можно сортировать одновременно на разных ядрах процессора.
- Работа с последовательным доступом: Алгоритм работает на данных с последовательным доступом, когда мы не можем в любой момент вернуться в начало, а должны работать с данными только в одном порядке (например, при сортировке связанных списков или потоковых данных).
- Интеграция: Если речь идет о пользовательских данных, принцип быстрой сортировки встроен даже в повседневные инструменты. Например, на вкладке «Главная» в группе «Сортировка и фильтр» в табличных процессорах, чтобы быстро сортировать по возрастанию, выбирается именно этот механизм под капотом.
Быстрая сортировка остается одним из самых популярных и эффективных алгоритмов (например, QuickSort или быстрая сортировка Хоара). Понимание того, как работает рекурсивный алгоритм разбиения, как боротся с повторяющимися элементами и как архитектура реального процессора влияет на скорость, позволяет писать по-настоящему быстрый и оптимизированный код.