C++/Algorytmy w STL/Operacje sortujące

sort()

void sort( RandomAccessIterator start, RandomAccessIterator end ) void sort( RandomAccessIterator start, RandomAccessIterator end, Compare cmp )

Działanie

sortuje ciąg rosnąco

Jak używać:

#include<algorithm>
...
sort( iterator start, iterator koniec );

//albo

sort( iterator start, iterator koniec, cmp ); //cmp - funkcja porównująca
...

W pierwszym przypadku algorytm sort() ustawia elementy w zakresie [start,koniec) w porządku niemalejącym. Gdy wywołujemy sortowanie z trzema parametrami to sortowanie odbywa się względem funkcji porównującej, którą definiujemy.

Przykładowe kody źródłowe

vector<int> v;
 v.push_back( 23 );
 v.push_back( -1 );
 v.push_back( 9999 );
 v.push_back( 0 );
 v.push_back( 4 );              

 cout << "Przed sortowaniem: ";
 for( int i = 0; i < v.size(); ++i ) {
   cout << v[i] << " ";
 }
 cout << endl;            

 sort( v.begin(), v.end() );            

 cout << "Po sortowaniu: ";
 for( int i = 0; i < v.size(); ++i ) {
   cout << v[i] << " ";
 }
 cout << endl;   

Efektem działania tego programu będzie:

Przed sortowaniem: 23 -1 9999 0 4
Po sortowaniu: -1 0 4 23 9999

Inny przykład, tym razem z funkcją definiowaną przez programistę:

bool cmp( int a, int b ) {
   return a > b;
 }              

 ...            

 vector<int> v;
 for( int i = 0; i < 10; ++i ) {
   v.push_back(i);
 }              

 cout << "Przed: ";
 for( int i = 0; i < 10; ++i ) {
   cout << v[i] << " ";
 }
 cout << endl;            

 sort( v.begin(), v.end(), cmp );               

 cout << "Po: ";
 for( int i = 0; i < 10; ++i ) {
   cout << v[i] << " ";
 }
 cout << endl; 

Wyniki działania takiego programu będą następujące:

Przed: 0 1 2 3 4 5 6 7 8 9
Po: 9 8 7 6 5 4 3 2 1 0

partial_sort()

void partial_sort( random_access_iterator start, random_access_iterator middle, random_access_iterator end )
void partial_sort( random_access_iterator start, random_access_iterator middle, random_access_iterator end, StrictWeakOrdering cmp )

Działanie

sortuje pierwsze N najmniejszych elementów w ciągu

partial_sort_copy()

random_access_iterator partial_sort_copy( input_iterator start, input_iterator end, random_access_iterator result_start, random_access_iterator result_end )
random_access_iterator partial_sort_copy( input_iterator start, input_iterator end, random_access_iterator result_start, random_access_iterator result_end, StrictWeakOrdering cmp )

Działanie

tworzy kopię N najmniejszych elementów ciągu

stable_sort()

void stable_sort( random_access_iterator start, random_access_iterator end )
void stable_sort( random_access_iterator start, random_access_iterator end, StrictWeakOrdering cmp )

Działanie

sortuje ciąg zachowując wzajemną kolejność dla równych elementów

nth_element()

void nth_element( random_access_iterator start, random_access_iterator nth, random_access_iterator end )
void nth_element( random_access_iterator start, random_access_iterator nth, random_access_iterator end, StrictWeakOrdering cmp )

Działanie

ciąg jest podzielony na nieposortowane grupy elementów mniejszych i większych od wybranego elementu Nth (odpowiednio po lewej i prawej jego stronie)