====== Algorytm stable_sort ======
Algorytm [[stable_sort]] sortuje elementy danego kontenera w porządku rosnącym korzystając z operatora < lub binarnego operatora relacji podanego jako argument. W odróżnieniu od algorytmu [[sort]], względna kolejność elementów równoważnych w kontenerze zostaje zachowana (algorytm jest stabilny).
===== Nagłówek =====
#include
===== Deklaracja stable_sort =====
template
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
template
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
===== Parametry =====
* //first// - pierwszy element kontenera
* //last// - element za ostatnim w kontenerze
* //comp// - operator binarny relacji odpowiadający operatorowi ///. Funkcja lub funktor postaci: //bool comp(const &a,const &b)// zwracająca //true// jeśli a
przykład użycia algorytmu stable_sort - książka telefoniczna
#include
#include
#include
using namespace std;
//klasa przechowująca rekord danych książki telefonicznej - imię, nazwisko i nr telefonu
class rekord
{
public:
string imie, nazwisko, tel; //składowe przechowujące właściwe dane
enum tryb {by_imie, by_nazwisko, by_tel}; //możliwe sposoby sortowania
static tryb comp_mode;//statyczna zmienna przechowująca sposób sortowania
//konstruktor
rekord(string im, string nazw, string t):imie(im),nazwisko(nazw),tel(t) {};
//operator porównania wykorzystywany przez algorytm stable_sort
bool operator <( const rekord& b ) const
{
switch(comp_mode)//wybór sortowanego pola
{
case by_imie: if(imie.compare(b.imie)<0)return true; break;
case by_nazwisko: if(nazwisko.compare(b.nazwisko)<0)return true;break;
case by_tel: if(tel.compare(b.tel)<0)return true; break;
}
return false;
};
//operator wpisu do strumienia - dla wygody drukowania rekordu
friend ostream& operator<<(ostream& str,const rekord& source);
};
rekord::tryb rekord::comp_mode; //statyczna zmienna przechowująca sposób sortowania
//funkcja porównująca w sposób odwrotny (zamiast operatora domyślnego)
//podawana jako trzeci argument algorytmu stable_sort
bool comparator(const rekord& a, const rekord& b)
{
switch(rekord::comp_mode)//wybór sortowanego pola
{
case rekord::by_imie: if(a.imie.compare(b.imie)>0)return true; break;
case rekord::by_nazwisko: if(a.nazwisko.compare(b.nazwisko)>0)return true;break;
case rekord::by_tel: if(a.tel.compare(b.tel)>0)return true; break;
}
return false;
}
//zaprzyjaźniony operator wpisu do strumienia ułatwiający drukowanie rekordu
ostream& operator<<(ostream& str,const rekord& source)
{
str.width(15);
str< spis; //wektor wpisów w książce telefonicznej
vector::iterator iter; //iterator dla wygody
//wpisujemy jakieś rekordy do książki w kolejności losowej
spis.push_back(rekord("Zbigniew", "Nowacki", "0-700700700"));
spis.push_back(rekord("Adam", "Czajkowski", "0202122"));
spis.push_back(rekord("Antonow", "Nowacki", "0-12345678"));
spis.push_back(rekord("Adam", "Zolowski", "222222222"));
spis.push_back(rekord("Jaroslaw", "Kwiatkowski", "0-800100100"));
spis.push_back(rekord("Sylwester", "Zolowski", "333333333"));
spis.push_back(rekord("Adam", "Garowy", "997"));
spis.push_back(rekord("Karol", "Zolowski", "87654321"));
cout<<"Ksiazka telefoniczna - przyklad uzycia algorytmu stable_sort";
cout<<"\nNieposortowana:\n";
//wypisujemy zawartość nieposortowanej książki
for(iter=spis.begin(); iter!=spis.end(); ++iter) cout<<*iter;
cout<<"\nPosortowana wedlug imion:\n";
//ustawiamy sposób sortowania na sortowanie po imionach
rekord::comp_mode=rekord::by_imie;
//wykonujemy sortowanie - funkcja sortuje wektor w podanym zakresie
//z użyciem domyślnego operatora porównania (operator <)
stable_sort (spis.begin(), spis.end());
//wypisujemy zawartość książki posortowanej po imionach
for (iter=spis.begin(); iter!=spis.end(); ++iter) cout << *iter;
cout<<"\nPosortowana wedlug nazwisk:\n";
//ustawiamy sposób sortowania na sortowanie po nazwiskach
rekord::comp_mode=rekord::by_nazwisko;
//wykonujemy sortowanie - książka zostaje posortowana względem nazwisk
//ale dla rekordów o tym samym nazwisku utrzymana zostaje kolejność
//pozostała po poprzednim sortowaniu czyli sortowanie po imionach
//nie występuje efekt zamiany kolejności elementów równych sobie
//umożliwia to sortowanie po wielu składowych klasy
stable_sort (spis.begin(), spis.end());
//wypisujemy ostatecznie posortowaną książkę
for (iter=spis.begin(); iter!=spis.end(); ++iter) cout << *iter;
cout<<"\nPosortowana wedlug nazwisk malejaco:\n";
//wykonujemy sortowanie z użyciem drugiej wersji algorytmu stable_sort
//tym razem zamiast wykorzystywać operator < zdefiniowany w klasie
//podamy jawnie funkcję używaną do porównania
//aby uwidocznić działanie tej funkcji odwraca ona sposób działania
//operatora porównania (działa jak operator >) co umożliwia sortowanie w porządku malejącym
//jest to rozwiązanie bardziej przejżyste niż przypisanie operatorowi < działania
//właściwego dla operatora >
//wcześniejsze sortowanie po imionach zostaje ciągle utrzymane
stable_sort (spis.begin(), spis.end(), comparator);
//wypisujemy ostatecznie posortowaną książkę
for (iter=spis.begin(); iter!=spis.end(); ++iter) cout << *iter;
cout<<"\nKoniec\n";
return 0;
}