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