Сорт (C++)

сорт је функција у C++ стандардној библиотеци која узима два итератора са насумичним приступом, за почетак и за крај, као аргументе и врши сортирање поређењем на елементима у сегменту између та два итератора, укључујући и крајеве сегмента. Алгоритам за сортирање може се разликовати између различитих имплементација. Стандардна ГНУ C++ библиотека, на пример, користи хибридни алгоритам за сортирање: прво се примени интросорт, до максималне дубине која се одређује формулом 2×лог₂ н, где је н број елемената, после чега се примени сортирање уметањем на резултат. Која год да је имплементација, комплексност би требало да буде О(нлогн) просечних поређења.

Примена

sort фуннкција се укључује преко algorithm заглавља стандардне C++ библиотеке, и прима три аргумента: RandomAccessIterator first, RandomAccessIterator last, Compare comp. Трећи аргумент има предодређену вредност - оператор "мање од" (<) за поређење елемената.

Овај пример кода сортира и штампа дати низ целих бројева (у растућем поретку). Показивачи на низ служе као итератори.

#include <iostream>
#include <algorithm>

int main() {
  int array[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
  int elements = sizeof(array) / sizeof(array[0]); 
  std::sort(array, array + elements);
  for (int i = 0; i < elements; ++i) 
     std::cout << array[i] << ' ';
}

Иста функционалност коришћењем контејнерског типа вецтор:

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

int main() {
  std::vector<int> vec;
  vec.push_back(10); vec.push_back(5); vec.push_back(100); 
  std::sort(vec.begin(), vec.end());
  for (int i = 0; i < vec.size(); ++i) 
     std::cout << vec[i] << ' ';
}

Други типови сортирања

сорт није стабилан: еквивалентни елементи који су постављени на један начин пре сортирања можда ће бити постављени на неки други после сортирања. стабле_сорт осигурава стабилност резултата по цени лошијих перформанси (у одређеним случајевима). Резултат партиал_сорт-а је Н сортираних елемената од M, осталих (M - Н) су остављени у недефинисаном редоследу. У зависности од дизајна, може испасти бржи од потпуног сортирања.

Неки контејнерски типови, међу њима и лист, пружају специјализовану верзију сорт-а као методу. Разлог томе је што код повезаних листа није могућ насумичан приступ (и стога се не може користити регуларна сорт функција); специјализована верзија такође чува вредности на које показују итератори листе.

Поређење са функцијом qсорт()

сорт() се може поредити са функцијом из стандардне C библиотеке qсорт() (из заглавља стдлиб.х). сорт користи шаблоне, тако да користи тачне функције за поређење за било који тип који се сортира, које су већ имплементиране за стандардне типове података. Иначе, може се навести функција за поређење, која се може проверити за тип од стране компилатора; док се код qсорт-а мора ручно вршити кастовање показивача на жељени тип на несигуран начин. Такође, qсорт приступа функцији за поређење преко показивача на функцију, што изискује велики број поновљених позива функције, што може утрошити доста времена; док код C++-а, функције за поређење су обично инлине-оване, што уклања потребу за позивом функције. У пракси, C++ код који користи сорт је чешће много бржи у сортирању података као што су цели бројеви од еквивалентног C кода који користи qсорт.

Литература

• Меyерс, Сцотт (2001). Еффецтиве СТЛ: 50 специфиц wаyс то импрове yоур усе оф тхе стандард темплате либрарy. Аддисон-Wеслеy. стр. 203. ISBN 0-201-74962-9. 

Спољашње везе

• C++ референца за std::sort
• Још једна C++ референца за std::sort