Jump to content

сортировка (С++)

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 ]

  1. ^ «Рабочий проект стандарта языка программирования C++» (PDF) . ИСО . п. 911.
  2. ^ Уильямс, Энтони (2002). «Сопряжение итераторов» (PDF) . Просто программные решения.
  3. ^ Оландер, Кристер (2005). Выяснение связей между парами итераторов, значений и ссылок . Учеб. Международная конференция. Генеративное программирование: концепции и опыт. ЛНКС . Том. 3676. стр. 342–356. CiteSeerX   10.1.1.184.8947 .
  4. ^ «Рабочий проект стандарта языка программирования C++» (PDF) . ИСО . п. 911.
  5. ^ ИСО / МЭК (2003). ISO/IEC 14882:2003(E): Языки программирования – C++ §25.3.1.1 sort [lib.sort], параграф. 2
  6. ^ « Общие алгоритмы », Дэвид Массер
  7. ^ Документация libstdc++: Алгоритм сортировки
  8. ^ стабильная_сортировка
  9. ^ Мартинес, Конрадо (2004). Частичная быстрая сортировка (PDF) . Учеб. 6-й семинар ACM-SIAM по алгоритмической разработке и экспериментам и 1-й семинар ACM-SIAM по аналитической алгоритмике и комбинаторике.
  10. ^ Мейерс, Скотт (2001). Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов . Аддисон-Уэсли. п. 203. ИСБН  0-201-74962-9 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 890e6e82ff60c34e63b1aaa465fe0db4__1673887200
URL1:https://arc.ask3.ru/arc/aa/89/b4/890e6e82ff60c34e63b1aaa465fe0db4.html
Заголовок, (Title) документа по адресу, URL1:
sort (C++) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)