сортировка (С++)
sort — это общая функция стандартной библиотеки C++, предназначенная для сортировки сравнения . Эта функция возникла в стандартной библиотеке шаблонов (STL).
Конкретный алгоритм сортировки не предусмотрен стандартом языка и может различаться в зависимости от реализации, но в наихудшем случае : вызов указана асимптотическая сложность функции sort должна выполнять не более O ( N log N ) сравнений при применении к диапазону из N элементов. [ 1 ]
Использование
[ редактировать ]The функция сортировки включена в Заголовок <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';
}
Та же функциональность с использованием векторный контейнер, используя его начать и конечные методы для получения итераторов:
#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';
}
родство
[ редактировать ]Сортировка определяется в общих чертах, так что она может работать с любым с произвольным доступом контейнером и любым способом определения того, что элемент x такого контейнера должен быть помещен перед другим элементом и .
Хотя в общих чертах указано, sort нелегко применить ко всем задачам сортировки. Конкретная проблема, ставшая предметом некоторого исследования, заключается в следующем:
- Позволять А и B — два массива, в которых существует некоторая связь между элементом A[i] и элемент B[i] для всех допустимых индексов я .
- Сортировать с Поддерживая отношения B , т. е. применить ту же перестановку к Б это сортирует А.
- Сделайте предыдущее, не копируя элементы А и B в новый массив пар , сортировку и перемещение элементов обратно в исходные массивы (для чего потребуется O ( n ) временного пространства).
Решение этой проблемы было предложено А. Уильямсом в 2002 году, который реализовал собственный тип итератора для пар массивов и проанализировал некоторые трудности корректной реализации такого типа итератора. [ 2 ] Решение Уильямса было изучено и уточнено К. Оландером. [ 3 ]
Сложность и реализации
[ редактировать ]Стандарт C++ требует, чтобы вызов sort выполняет сравнения O ( N log N ) при применении к диапазону из N элементов. [ 4 ] В предыдущих версиях C++, таких как C++03 , только средняя сложность должна была быть O ( N log N ) . [ 5 ] Это должно было позволить использовать такие алгоритмы, как быстрая сортировка (медиана из 3) , которые работают быстро в среднем случае, действительно значительно быстрее, чем другие алгоритмы, такие как сортировка кучи , с оптимальной сложностью в наихудшем случае, и где квадратичная сложность в худшем случае встречается редко. [ 6 ] Внедрение гибридных алгоритмов, таких как интросорт, позволило обеспечить как высокую среднюю производительность, так и оптимальную производительность в наихудшем случае, поэтому в более поздних стандартах требования к сложности были ужесточены.
В разных реализациях используются разные алгоритмы. Библиотека GNU Standard C++ , например, использует гибридный алгоритм сортировки, состоящий из трех частей: сначала выполняется интросорт (сама интросорт представляет собой гибрид быстрой сортировки и пирамидальной сортировки) до максимальной глубины, определяемой 2×log 2 n , где n — количество элементов, за которым следует сортировка вставкой результата. [ 7 ]
Другие виды сортировки
[ редактировать ]sort
нестабилен: эквивалентные элементы, которые до сортировки упорядочены в одном порядке, после сортировки могут быть упорядочены по-другому. stable_sort
обеспечивает стабильность результата за счет худшей производительности (в некоторых случаях), требуя только квазилинейного времени с показателем степени 2 – O( n log 2 n ) – если дополнительная память недоступна, но линейное время O( n log n ), если дополнительная память доступна. [ 8 ] Это позволяет использовать сортировку слиянием на месте для стабильной сортировки на месте и обычную сортировку слиянием для стабильной сортировки с дополнительной памятью.
Частичная сортировка реализуется частичная_сортировка , которая принимает диапазон из n элементов и целое число m < n и переупорядочивает диапазон так, чтобы наименьшие m элементов находились в первых m позициях в отсортированном порядке (оставляя оставшиеся n − m в оставшихся позициях, в некоторых неуказанных позициях). заказ). В зависимости от конструкции это может быть значительно быстрее, чем полная сортировка. Исторически это обычно реализовывалось с использованием алгоритма на основе кучи , который занимает время Θ( n + m log n ) в худшем случае. лучший алгоритм, называемый быстрой сортировкой В реализации Copenhagen STL используется , в результате чего сложность снижается до Θ( n + m log m ) . [ 9 ]
Выбор -го элемента n реализуется nth_element
, который фактически реализует частичную сортировку на месте: он правильно сортирует n- й элемент, а также гарантирует, что этот элемент разбивается так, что элементы до него меньше его, а элементы после него больше его. Существует требование, чтобы в среднем это занимало линейное время, но не существует требования наихудшего случая; Этим требованиям в точности соответствует fastselect для любого выбора стратегии поворота.
Некоторые контейнеры, среди них list
, предоставить специализированную версию sort
как функция-член. Это связано с тем, что связанные списки не имеют произвольного доступа (и, следовательно, не могут использовать обычные sort
функция); а специализированная версия также сохраняет значения, на которые указывают итераторы списка значений.
Сравнение с qsort
[ редактировать ]Помимо sort , стандартная библиотека C++ также включает в себя qsort из стандартной библиотеки C. По сравнению с qsort , шаблон сортировка более типобезопасна, поскольку не требует доступа к элементам данных через unsafe. недействительные указатели, как qsort делает. Также, qsort обращается к функции сравнения, используя указатель функции, что требует большого количества повторных вызовов функции, тогда как в sort функции сравнения могут быть встроены в пользовательский объектный код, созданный для создания экземпляра шаблона. На практике код C++, использующий sort часто значительно быстрее сортирует простые данные, такие как целые числа, чем эквивалентный код C, использующий qсорт . [ 10 ]
Ссылки
[ редактировать ]- ^ «Рабочий проект стандарта языка программирования C++» (PDF) . ИСО . п. 911.
- ^ Уильямс, Энтони (2002). «Сопряжение итераторов» (PDF) . Просто программные решения.
- ^ Оландер, Кристер (2005). Выяснение связей между парами итераторов, значений и ссылок . Учеб. Международная конференция. Генеративное программирование: концепции и опыт. ЛНКС . Том. 3676. стр. 342–356. CiteSeerX 10.1.1.184.8947 .
- ^ «Рабочий проект стандарта языка программирования C++» (PDF) . ИСО . п. 911.
- ^ ИСО / МЭК (2003). ISO/IEC 14882:2003(E): Языки программирования – C++ §25.3.1.1 sort [lib.sort], параграф. 2
- ^ « Общие алгоритмы », Дэвид Массер
- ^ Документация libstdc++: Алгоритм сортировки
- ^ стабильная_сортировка
- ^ Мартинес, Конрадо (2004). Частичная быстрая сортировка (PDF) . Учеб. 6-й семинар ACM-SIAM по алгоритмической разработке и экспериментам и 1-й семинар ACM-SIAM по аналитической алгоритмике и комбинаторике.
- ^ Мейерс, Скотт (2001). Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов . Аддисон-Уэсли. п. 203. ИСБН 0-201-74962-9 .