сортировка (C ++) - sort (C++)

sort - это общая функция в стандартной библиотеке C ++ для выполнения сравнительной сортировки . Функция возникла в стандартной библиотеке шаблонов (STL).

Конкретный алгоритм сортировки не предусмотрен стандартом языка и может варьироваться в зависимости от реализации, но указана асимптотическая сложность функции наихудшего случая : вызов sort должен выполнять O ( N log N ) сравнений при применении к диапазону N элементы.

Применение

Функция сортировки включена из заголовка <algorithm> стандартной библиотеки C ++ и имеет три аргумента : сначала RandomAccessIterator, последний - RandomAccessIterator, Compare comp . Здесь RandomAccessIterator - это шаблонный тип, который должен быть итератором с произвольным доступом , а первый и последний должны определять последовательность значений, т. Е. Последний должен быть доступен от первого путем повторного применения оператора приращения к первому . Третий аргумент, также имеющий шаблонный тип, обозначает предикат сравнения. Этот предикат сравнения должен определять строгий слабый порядок элементов сортируемой последовательности. Третий аргумент не обязателен; если не указан, используется оператор «меньше» ( < ), который может быть перегружен в C ++.

Этот пример кода сортирует заданный массив целых чисел (в порядке возрастания) и распечатывает его. 

#include <algorithm>
#include <iostream>

int main() {
  int array[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
  std::sort(std::begin(array), std::end(array));
  for (size_t i = 0; i < std::size(array); ++i) {
     std::cout << array[i] << ' ';
  }
  std::cout << '\n';
}

Та же функциональность с использованием векторного контейнера с использованием его методов begin и end для получения итераторов: 

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
  std::sort(vec.begin(), vec.end());
  for (size_t i = 0; i < vec.size(); ++i) {
     std::cout << vec[i] << ' ';
  }
  std::cout << '\n';
}

Универсальность

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

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

  • Пусть A и B - два массива, где существует некоторая связь между элементом A [i] и элементом B [i] для всех допустимых индексов i .
  • Сортировка , сохраняя при этом связь с B , то есть применить ту же перестановку к B , которая сортирует А .
  • Выполните предыдущее без копирования элементов A и B в новый массив пар , сортировки и перемещения элементов обратно в исходные массивы (для чего потребуется временное пространство O ( n ) ).

Решение этой проблемы было предложено А. Уильямсом в 2002 году, который реализовал настраиваемый тип итератора для пар массивов и проанализировал некоторые трудности, связанные с правильной реализацией такого типа итератора. Решение Вильямса было изучено и уточнено К. Аландером.

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

Стандарт C ++ требует, чтобы при вызове sort выполнялось O ( N log N ) сравнений при применении к диапазону из N элементов. В предыдущих версиях C ++, таких как C ++ 03 , требовалось, чтобы только средняя сложность составляла O ( N log N ) . Это должно было позволить использовать такие алгоритмы, как (median-of-3) quicksort , которые являются быстрыми в среднем случае, действительно значительно быстрее, чем другие алгоритмы, такие как сортировка кучи с оптимальной сложностью наихудшего случая, и где квадратичная сложность наихудшего случая встречается редко. Внедрение гибридных алгоритмов, таких как внутренняя сортировка, обеспечило как высокую среднюю производительность, так и оптимальную производительность в худшем случае, и, таким образом, требования к сложности были ужесточены в более поздних стандартах.

В разных реализациях используются разные алгоритмы. В библиотеке GNU Standard C ++ , например, использует алгоритм 3-часть гибридной сортировки: introsort сначала выполняется (introsort само по себе является гибридом быстрой сортировки и кучи рода), на глубину максимальной заданной 2 × войти 2 п , где п является количество элементов с последующей сортировкой вставкой по результату.

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

Сортировка нестабильна: эквивалентные элементы, упорядоченные в одном порядке перед сортировкой, могут быть упорядочены по-разному после сортировки. stable_sort обеспечивает стабильность результата за счет худшей производительности (в некоторых случаях), требуя только квазилинейное время с показателем 2 - O ( n log 2 n ) - если дополнительная память недоступна, но линейное время O ( n log n ), если дополнительная память доступна. Это позволяет использовать сортировку слиянием на месте для стабильной сортировки на месте и регулярную сортировку слиянием для стабильной сортировки с дополнительной памятью.

Частичная сортировка реализуется функцией partial_sort , которая принимает диапазон из n элементов и целое число m < n и переупорядочивает диапазон так, чтобы наименьшие m элементов находились в первых m позициях в отсортированном порядке (оставляя оставшиеся n - m в оставшихся позиции в неустановленном порядке). В зависимости от дизайна это может быть значительно быстрее, чем полная сортировка. Исторически это обычно реализовывалось с использованием алгоритма на основе кучи , который занимал Θ ( n + m log n ) в худшем случае. В копенгагенской реализации STL используется более совершенный алгоритм, называемый быстрой сортировкой , что снижает сложность до ( n + m log m ) .

Выбор из п - го элемента осуществляется nth_element , который фактически реализует парциальное то на месте: он правильно сортирует п - й элемент, а также гарантирует , что этот элемент перегородки так , элементы перед ней меньше , чем она, и элементы после него являются больше, чем это. Требуется, чтобы это занимало в среднем линейное время, но нет требования наихудшего случая; Эти требования точно выполняются функцией quickselect при любом выборе стратегии разворота.

Некоторые контейнеры, в том числе список , предоставляют специализированную версию сортировки в качестве функции-члена. Это связано с тем, что связанные списки не имеют произвольного доступа (и, следовательно, не могут использовать обычную функцию сортировки ); а специализированная версия также сохраняет итераторы списка значений, на которые указывают.

Сравнение с qsort

Помимо рода , С ++ стандартная библиотека включает в себя QSort функции из стандартной библиотеки C . По сравнению с qsort шаблонная сортировка более безопасна по типу, поскольку не требует доступа к элементам данных через небезопасные указатели void , как это делает qsort . Кроме того, qsort обращается к функции сравнения с помощью указателя функции, что требует большого количества повторных вызовов функций, тогда как при сортировке функции сравнения могут быть встроены в пользовательский объектный код, созданный для создания экземпляра шаблона. На практике код C ++, использующий sort , часто значительно быстрее сортирует простые данные, такие как целые числа, чем эквивалентный код C, использующий qsort .

Рекомендации

Внешние ссылки