Sort (C++)

sort je funkcija u C++ standardnoj biblioteci koja uzima dva iteratora sa nasumičnim pristupom, za početak i za kraj, kao argumente i vrši sortiranje poređenjem na elementima u segmentu između ta dva iteratora, uključujući i krajeve segmenta. Algoritam za sortiranje može se razlikovati između različitih implementacija. Standardna GNU C++ biblioteka, na primer, koristi hibridni algoritam za sortiranje: prvo se primeni introsort, do maksimalne dubine koja se određuje formulom 2×log₂ n, gde je n broj elemenata, posle čega se primeni sortiranje umetanjem na rezultat. Koja god da je implementacija, kompleksnost bi trebalo da bude O(nlogn) prosečnih poređenja.

Primena

sort funnkcija se uključuje preko algorithm zaglavlja standardne C++ biblioteke, i prima tri argumenta: RandomAccessIterator first, RandomAccessIterator last, Compare comp. Treći argument ima predodređenu vrednost - operator "manje od" (<) za poređenje elemenata.

Ovaj primer koda sortira i štampa dati niz celih brojeva (u rastućem poretku). Pokazivači na niz služe kao iteratori.

#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] << ' ';
}

Ista funkcionalnost korišćenjem kontejnerskog tipa vector:

#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] << ' ';
}

Drugi tipovi sortiranja

sort nije stabilan: ekvivalentni elementi koji su postavljeni na jedan način pre sortiranja možda će biti postavljeni na neki drugi posle sortiranja. stable_sort osigurava stabilnost rezultata po ceni lošijih performansi (u određenim slučajevima). Rezultat partial_sort-a je N sortiranih elemenata od M, ostalih (M - N) su ostavljeni u nedefinisanom redosledu. U zavisnosti od dizajna, može ispasti brži od potpunog sortiranja.

Neki kontejnerski tipovi, među njima i list, pružaju specijalizovanu verziju sort-a kao metodu. Razlog tome je što kod povezanih lista nije moguć nasumičan pristup (i stoga se ne može koristiti regularna sort funkcija); specijalizovana verzija takođe čuva vrednosti na koje pokazuju iteratori liste.

Poređenje sa funkcijom qsort()

sort() se može porediti sa funkcijom iz standardne C biblioteke qsort() (iz zaglavlja stdlib.h). sort koristi šablone, tako da koristi tačne funkcije za poređenje za bilo koji tip koji se sortira, koje su već implementirane za standardne tipove podataka. Inače, može se navesti funkcija za poređenje, koja se može proveriti za tip od strane kompilatora; dok se kod qsort-a mora ručno vršiti kastovanje pokazivača na željeni tip na nesiguran način. Takođe, qsort pristupa funkciji za poređenje preko pokazivača na funkciju, što iziskuje veliki broj ponovljenih poziva funkcije, što može utrošiti dosta vremena; dok kod C++-a, funkcije za poređenje su obično inline-ovane, što uklanja potrebu za pozivom funkcije. U praksi, C++ kod koji koristi sort je češće mnogo brži u sortiranju podataka kao što su celi brojevi od ekvivalentnog C koda koji koristi qsort.

Literatura

• Meyers, Scott (2001). Effective STL: 50 specific ways to improve your use of the standard template library. Addison-Wesley. стр. 203. ISBN 0-201-74962-9. 

Spoljašnje veze

• C++ referenca za std::sort
• Još jedna C++ referenca za std::sort