Введение

sort — это универсальная функция в стандартной библиотеке C++, предназначенная для сортировки сравнением. Функция берет свое начало в библиотеке стандартных шаблонов (STL). Конкретный алгоритм сортировки не определен стандартом языка и может различаться в разных реализациях, однако гарантируется, что в худшем случае асимптотическая сложность функции не превышает [[линейно-логарифмическое число сравнений при применении к диапазону из N элементов.

Общность

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

Пусть `a` и `b` – два массива, для которых существует некоторое отношение между элементом `a[i]` и элементом `b[i]` для всех допустимых индексов `i`. Необходимо отсортировать массив `a`, сохраняя отношение с массивом `b`, то есть применить ту же перестановку к массиву `b`, которая сортирует массив `a`. Реализовать это без копирования элементов `a` и `b` в новый массив пар, последующей сортировки и возврата элементов в исходные массивы (что потребовало бы O(n) дополнительной памяти). Решение этой задачи было предложено А. Уильямсом в 2002 году, который реализовал пользовательский тип итератора для пар массивов и проанализировал некоторые трудности, связанные с правильной реализацией такого типа итератора. Решение Уильямса было изучено и доработано К. Оландером.

Сложность и реализация

Стандарт C++ требует, чтобы вызов выполнял [[линеарифметическое] количество сравнений при применении к диапазону из N элементов. В предыдущих версиях C++, таких как C++03, требовалась только средняя сложность O(N log N). Это позволяло использовать алгоритмы, такие как быстрая сортировка с выбором медианы из трех элементов, которые были быстры в среднем случае, значительно быстрее, чем другие алгоритмы, такие как сортировка кучей с оптимальной сложностью в худшем случае, и где квадратичная сложность в худшем случае возникала редко. Введение гибридных алгоритмов, таких как интроспективная сортировка, позволило достичь как высокой средней производительности, так и оптимальной производительности в худшем случае, поэтому требования к сложности были ужесточены в более поздних стандартах. Различные реализации используют разные алгоритмы. Например, библиотека GNU Standard C++ использует трехэтапный гибридный алгоритм сортировки: сначала выполняется интроспективная сортировка (которая сама является гибридом быстрой сортировки и сортировки кучей) до максимальной глубины, равной 2 × log2 n, где n — количество элементов, а затем выполняется сортировка вставками для упорядоченного результата.

Другие виды сортировки

сортировка не является стабильной: эквивалентные элементы, упорядоченные одним способом до сортировки, могут быть упорядочены иначе после сортировки. Стабильная сортировка обеспечивает стабильность результата за счет снижения производительности (в некоторых случаях), требуя лишь квазилинейного времени со степенью 2 – O(n log₂ n) – если дополнительная память недоступна, но логарифмически-линейного времени O(n log n) при наличии дополнительной памяти. Это позволяет использовать сортировку слиянием на месте для стабильной сортировки на месте и обычную сортировку слиянием для стабильной сортировки с использованием дополнительной памяти. Частичная сортировка реализована функцией, которая принимает диапазон из n элементов и целое число m < n, и переупорядочивает диапазон так, чтобы наименьшие m элементов находились в первых m позициях в отсортированном порядке (оставляя остальные n − m элементов на оставшихся позициях в некотором неопределенном порядке). В зависимости от реализации это может быть значительно быстрее, чем полная сортировка. Исторически это часто реализовывалось с помощью алгоритма на основе кучи, который имеет сложность Θ(n + m log n) в наихудшем случае. В реализации Copenhagen STL используется более эффективный алгоритм под названием quickselsort, снижающий сложность до Θ(n + m log m). Выбор n-го элемента реализован функцией nth_element, которая фактически реализует частичную сортировку: она правильно располагает n-й элемент, а также гарантирует, что все элементы перед ним меньше его, а все элементы после него больше его. Требуется, чтобы в среднем это занимало линейное время, но нет требований к наихудшему случаю; эти требования точно выполняются алгоритмом quickselect для любой стратегии выбора опорного элемента. Некоторые контейнеры, включая list, предоставляют специализированную версию сортировки в виде метода-члена. Это связано с тем, что связные списки не имеют произвольного доступа (и, следовательно, не могут использовать обычную функцию сортировки), а специализированная версия также сохраняет значения, на которые указывают итераторы списка.

Сравнение с qsort

Кроме `std::swap`, стандартная библиотека C++ также включает в себя функцию `swap` из стандартной библиотеки C. По сравнению с `std::swap`, шаблонный `std::swap` более типобезопасен, поскольку не требует доступа к элементам данных через небезопасные указатели, как это делает `swap`. Кроме того, `swap` обращается к функции сравнения с помощью указателя функции, что требует большого количества повторяющихся вызовов функций, в то время как в `std::swap`, функции сравнения могут быть встроены в пользовательский объектный код, сгенерированный для конкретной специализации шаблона. На практике, код C++ с использованием `std::swap` часто значительно быстрее сортирует простые данные, такие как целые числа, чем эквивалентный код C, использующий `swap`.