Narzędzia użytkownika

Narzędzia witryny


stable_sort

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<algorithm> 

Deklaracja stable_sort

 template <class RandomAccessIterator>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
 
template <class RandomAccessIterator, class Compare>
  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 <typ> &a,const <typ> &b) zwracająca true jeśli a<b (element a leży przed elementem b w ustalonym porządku logicznym) oraz false w przeciwnym przypadku.

Wartość zwracana

Brak.

Działanie

Wykonuje sortowanie elementów kontenera w porządku ustalonym przez operator < (domyślnie rosnący) lub operator comp podany jako argument.

Przykład użycia

przykład użycia algorytmu stable_sort - książka telefoniczna
#include <iostream>
#include <algorithm>
#include <vector>
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<<left<<source.nazwisko.c_str();
	str.width(15);
	str<<left<<source.imie.c_str();
	str.width(15);
	str<<left<<source.tel.c_str()<<endl;
	return str;
};
 
//------------------------------------------------------------------------------------------
// pętla główna
int main () {
  vector<rekord> spis; //wektor wpisów w książce telefonicznej
  vector<rekord>::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;
}
stable_sort.txt · ostatnio zmienione: 2008/12/10 22:26 przez vtech