Сортировка (C ++) - Sort (C++)

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

Конкретные алгоритм сортировки не предписывается языковым стандартом и может различаться в зависимости от реализации, но худший случай асимптотический указана сложность функции: вызов Сортировать должен выполнять О(N бревно N) сравнения при применении к ряду N элементы.[1]

использование

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

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

#включают <algorithm>#включают <iostream>с помощью пространство имен стандартное;int главный() {  int множество[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };  size_t размер = размер(множество) / размер(множество[0]);   Сортировать(множество, множество + размер);  за (size_t я = 0; я < размер; ++я) {     cout << множество[я] << ' ';  }  cout << конец;}

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

#включают <algorithm>#включают <iostream>#включают <vector>с помощью пространство имен стандартное;int главный() {  вектор<int> vec { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };  Сортировать(vec.начинать(), vec.конец());  за (int я = 0; я < vec.размер(); ++я) {     cout << vec[я] << ' ';  }  cout << конец;}

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

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

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

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

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

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

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

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

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

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

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

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

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

Сравнение с qsort

Помимо Сортироватьстандартная библиотека C ++ также включает qsort функция от Стандартная библиотека C. В сравнении с qsort, шаблонный Сортировать более безопасен по типу, поскольку не требует доступа к элементам данных через небезопасный пустота указатели, как qsort делает. Также, qsort обращается к функции сравнения с помощью указателя функции, что требует большого количества повторных вызовов функций, тогда как в Сортировать, функции сравнения могут быть встроенный в пользовательский объектный код, созданный для создания экземпляра шаблона. На практике код C ++ с использованием Сортировать часто значительно быстрее сортирует простые данные, такие как целые числа, чем эквивалентный код C, использующий qsort.[10]

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

  1. ^ «Рабочий проект стандарта языка программирования C ++» (PDF). ISO. п. 911.
  2. ^ Уильямс, Энтони (2002). "Объединение итераторов" (PDF). Просто программные решения.
  3. ^ Аландер, Кристер (2005). Выявление отношений между парами итераторов, значений и ссылок. Proc. Междунар. Конф. Генеративное программирование: концепции и опыт. LNCS. 3676. С. 342–356. CiteSeerX  10.1.1.184.8947.
  4. ^ «Рабочий проект стандарта языка программирования C ++» (PDF). ISO. п. 911.
  5. ^ ISO /IEC (2003). ISO / IEC 14882: 2003 (E): Языки программирования - C ++ §25.3.1.1 сортировка [lib.sort] пункт 2
  6. ^ "Общие алгоритмы ", Дэвид Массер
  7. ^ Документация libstdc ++: Алгоритм сортировки
  8. ^ stable_sort
  9. ^ Мартинес, Конрадо (2004). Частичная быстрая сортировка (PDF). Proc. 6-й семинар ACM-SIAM по разработке алгоритмов и экспериментам и 1-й семинар ACM-SIAM по аналитической алгоритмике и комбинаторике.
  10. ^ Мейерс, Скотт (2001). Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов. Эддисон-Уэсли. п. 203. ISBN  0-201-74962-9. Cite имеет пустой неизвестный параметр: | соавторы = (помощь)

внешняя ссылка