Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
partial_sort [2008/12/12 12:16] alaskow1 |
partial_sort [2008/12/12 13:39] alaskow1 |
||
---|---|---|---|
Linia 34: | Linia 34: | ||
===== Opis algorytmu ===== | ===== Opis algorytmu ===== | ||
- | Przemieszcza elementy w kolekcji w zakresie [first, last) tak, że w zakresie [first, middle) zawiera najmniejsze elementy z całego zakresu sortowania kolekcji, a w zakresie [middle, last) znajdują się pozostałe, nieuporządkowane elementy. | + | Przemieszcza elementy w kolekcji w zakresie [**first**, **last**) tak, że w zakresie [**first**, **middle**) zawiera najmniejsze elementy z całego zakresu sortowania kolekcji, a w zakresie [**middle**, **last**) znajdują się pozostałe, nieuporządkowane elementy. |
- | Do porównywania obiektów w kolekcji funkcja wykorzystuje albo zdefiniowany dla obiektu operator <code cpp>operator<</code> w pierwszej wersji funkcji, albo zewnętrzną funkcję/funktor porównujący w wersji drugiej. | + | Do porównywania obiektów w kolekcji funkcja wykorzystuje albo zdefiniowany dla obiektu operator mniejszości w pierwszej wersji funkcji, albo zewnętrzną funkcję/funktor porównujący w wersji drugiej. |
==== Złożoność algorytmu ==== | ==== Złożoność algorytmu ==== | ||
Linia 42: | Linia 42: | ||
Do sortowania elementów wykorzystano algorytm **heapsort**, więc jego złożoność można oszacować wg poniższego wzoru: | Do sortowania elementów wykorzystano algorytm **heapsort**, więc jego złożoność można oszacować wg poniższego wzoru: | ||
- | <tex>O = (last - start)*log(middle - start)</tex> | + | <code>O = (last - start)*log(middle - start)</code> |
+ | ===== Przykłady użycia ===== | ||
+ | ==== Przykład pierwszy ==== | ||
+ | W tym przykładzie użyto pierwszej wersji omawianej funkcji do odnalezienia 4 najmniejszych liczb całkowitych typu **int** w kolekcji: | ||
+ | <code cpp> | ||
+ | vector<int> first; //Kolekcja liczb całkowitych | ||
+ | vector<int>::iterator iter; //Iterator do tej kolekcji | ||
+ | /* Wypełnianie kolekcji przykładowymi liczbami */ | ||
+ | first.push_back(23); | ||
+ | first.push_back(16); | ||
+ | first.push_back(54); | ||
+ | first.push_back(21); | ||
+ | first.push_back(14); | ||
+ | first.push_back(38); | ||
+ | first.push_back(63); | ||
+ | first.push_back(29); | ||
+ | cout << "Przyklad pierwszy\n\n"; | ||
+ | cout << "Liczby calkowite 'int':\n\n"; | ||
+ | /* Wyświetlenie zawartości kolekcji */ | ||
+ | for (iter = first.begin(); iter != first.end(); ++iter) | ||
+ | cout << *iter << " "; | ||
+ | /* out: 23 16 54 21 14 38 63 29 */ | ||
+ | |||
+ | /* Sortowanie kolekcji, do uzyskania 4 posortowanych elementów */ | ||
+ | partial_sort(first.begin(), first.begin() + 4, first.end()); | ||
+ | |||
+ | cout << "\n\nDane czesciowo posortowane - pierwsze 4 elementy:\n\n"; | ||
+ | |||
+ | /* Wyświetlenie zawartości częściowo posortowanej kolekcji */ | ||
+ | for (iter = first.begin(); iter != first.end(); ++iter) | ||
+ | cout << *iter << " "; | ||
+ | |||
+ | /* out: 14 16 21 23 54 38 63 29 */ | ||
+ | </code> | ||
+ | |||
+ | ==== Przykład drugi ==== | ||
+ | |||
+ | W tym przykładzie sortowana będzie kolekcja następujących obiektów, modelujących kartę pacjenta: | ||
+ | |||
+ | <code cpp> | ||
+ | /* Rodzaj sortowania */ | ||
+ | enum SortBy {byName, byAge, byWeight}; | ||
+ | |||
+ | class PatientCard { | ||
+ | private: | ||
+ | string name; //Nazwisko | ||
+ | int age; //Wiek | ||
+ | double weight; //Waga | ||
+ | |||
+ | static SortBy sort; //Rodzaj sortowania | ||
+ | public: | ||
+ | /* Konstruktor zerowy. */ | ||
+ | PatientCard() : name("name"), age(0), weight(0.0) {} | ||
+ | /* Konstruktor inicjujący. */ | ||
+ | PatientCard(const string& _name, const int& _age, const double& _weight) : | ||
+ | name(_name), age(_age), weight(_weight) {} | ||
+ | |||
+ | const string& getName() const { //Zwraca nazwisko | ||
+ | return name; | ||
+ | } | ||
+ | |||
+ | const int getAge() const { //Zwraca wiek | ||
+ | return age; | ||
+ | } | ||
+ | |||
+ | const double getWeight() const { //Zwraca wagę | ||
+ | return weight; | ||
+ | } | ||
+ | |||
+ | void setSort(SortBy _sort) { //Ustala rodzaj sortowania | ||
+ | sort = _sort; | ||
+ | } | ||
+ | |||
+ | /* Operator mniejszości, służący do porównywania w algorytmie. Porównuje | ||
+ | odpowiednie pola dwóch obiektów, zwraca 'true', jeśli są uporządkowane | ||
+ | rosnąco, i 'false', jeśli nie. Do wyboru pól do porównywania służy pole | ||
+ | 'sort'. */ | ||
+ | bool operator<(const PatientCard& _card) { | ||
+ | switch (sort) { | ||
+ | case byName: | ||
+ | if (name.compare(_card.name) < 0) | ||
+ | return true; | ||
+ | break; | ||
+ | case byAge: | ||
+ | if (age < _card.age) | ||
+ | return true; | ||
+ | break; | ||
+ | case byWeight: | ||
+ | if (weight < _card.weight) | ||
+ | return true; | ||
+ | break; | ||
+ | default: | ||
+ | return false; | ||
+ | } | ||
+ | |||
+ | return false; | ||
+ | }; | ||
+ | |||
+ | /* Zaprzyjaźniony operator, pozwalający na wysłanie danych obiektu do | ||
+ | strumienia wyjściowego. */ | ||
+ | friend ostream& operator<<(ostream& _cout, const PatientCard& _card); | ||
+ | }; | ||
+ | |||
+ | SortBy PatientCard::sort = byName; //Inicjacja statycznego pola 'sort' | ||
+ | |||
+ | /* Zaprzyjaźniony operator. */ | ||
+ | ostream& operator<<(ostream& _cout, const PatientCard& _card) { | ||
+ | _cout << _card.name << "\n\t\twiek: " << _card.age << "\twaga: " << _card.weight << endl; | ||
+ | |||
+ | return _cout; | ||
+ | } | ||
+ | |||
+ | int main() { | ||
+ | vector<PatientCard> second; //Kolekcja kart pacjenta | ||
+ | vector<PatientCard>::iterator iter2; //Iterator do tej kolekcji | ||
+ | |||
+ | /* Wypełnienie kolekcji przykładowymi danymi */ | ||
+ | second.push_back(PatientCard("Wilson", 32, 78.5)); | ||
+ | second.push_back(PatientCard("Pearson", 27, 63.2)); | ||
+ | second.push_back(PatientCard("Kingsley", 43, 89.0)); | ||
+ | second.push_back(PatientCard("Smith", 18, 57.4)); | ||
+ | second.push_back(PatientCard("Wiliams", 22, 82.1)); | ||
+ | second.push_back(PatientCard("Crouch", 37, 102.6)); | ||
+ | second.push_back(PatientCard("Michelson", 64, 96.4)); | ||
+ | second.push_back(PatientCard("Bright", 54, 60.5)); | ||
+ | |||
+ | vector<PatientCard> third = second; //Kolejne kolekcje | ||
+ | vector<PatientCard> fourth = second; | ||
+ | |||
+ | </code> | ||
+ | |||
+ | === Sortowanie wg wbudowanego operatora mniejszości === | ||
+ | |||
+ | Tu sortowanie odbywa się przy użyciu wbudowanego operatora mniejszości, który przy obecnym ustawieniu pola **sort** sortuje karty alfabetycznie. Chcemy zatem uzyskać trzy pierwsze karty: | ||
+ | |||
+ | <code cpp> | ||
+ | partial_sort(second.begin(), second.begin() + 3, second.end()); | ||
+ | |||
+ | /* out: Bright | ||
+ | wiek: 54 waga: 60.5 | ||
+ | Crouch | ||
+ | wiek: 37 waga: 102.6 | ||
+ | Kingsley | ||
+ | wiek: 43 waga: 89 | ||
+ | Wiliams | ||
+ | wiek: 22 waga: 82.1 | ||
+ | Smith... */ | ||
+ | </code> | ||
+ | |||
+ | === Sortowanie wg zewnętrznej funkcji porównującej === | ||
+ | |||
+ | W tym przypadku zdefiniowano zewnętrzną funkcję, służącą do porównywania kart i sortowania ich według malejącej wagi: | ||
+ | |||
+ | <code cpp> | ||
+ | bool compareCard(const PatientCard& _a, const PatientCard& _b) { | ||
+ | if (_a.getWeight() > _b.getWeight()) | ||
+ | return true; | ||
+ | return false; | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | Chcemy uzyskać cztery karty o największej wadze: | ||
+ | |||
+ | <code cpp> | ||
+ | partial_sort(third.begin(), third.begin() + 4, third.end(), compareCard); | ||
+ | |||
+ | /* out: Crouch | ||
+ | wiek: 37 waga: 102.6 | ||
+ | Michelson | ||
+ | wiek: 64 waga: 96.4 | ||
+ | Kingsley | ||
+ | wiek: 43 waga: 89 | ||
+ | Wiliams | ||
+ | wiek: 22 waga: 82.1 | ||
+ | Smith | ||
+ | wiek: 18 waga: 57.4 | ||
+ | Pearson | ||
+ | wiek: 27 waga: 63.2 | ||
+ | ... */ | ||
+ | </code> | ||
+ | |||
+ | === Sortowanie wg zdefiniowanego funktora === | ||
+ | |||
+ | Funktor, czyli obiekt funkcyjny, to taki obiekt, który ma zdefiniowany operator **operator()**. W ogólnym przypadku funktor może przechowywać stan, który może mieć wpływ na działanie tego operatora, w przeciwieństwie do stałej w działaniu funkcji porównującej. W tym przypadku jednak ograniczono się do najprostszego przypadku funktora: | ||
+ | |||
+ | <code cpp> | ||
+ | class functorCard { | ||
+ | public: | ||
+ | bool operator()(const PatientCard& _a, const PatientCard& _b) { | ||
+ | if (_a.getAge() > _b.getAge()) | ||
+ | return true; | ||
+ | |||
+ | return false; | ||
+ | } | ||
+ | }; | ||
+ | |||
+ | </code> | ||
+ | |||
+ | Jak widać, funktor umożliwia sortowanie wg malejącego wieku. Chcemy uzyskać pięć kart o największym wieku: | ||
+ | |||
+ | <code cpp> | ||
+ | partial_sort(fourth.begin(), fourth.begin() + 5, fourth.end(), functorCard()); | ||
+ | |||
+ | /* out: Michelson | ||
+ | wiek: 64 waga: 96.4 | ||
+ | Bright | ||
+ | wiek: 54 waga: 60.5 | ||
+ | Kingsley | ||
+ | wiek: 43 waga: 89 | ||
+ | Crouch | ||
+ | wiek: 37 waga: 102.6 | ||
+ | Wilson | ||
+ | wiek: 32 waga: 78.5 | ||
+ | Smith | ||
+ | wiek: 18 waga: 57.4 | ||
+ | Wiliams | ||
+ | wiek: 22 waga: 82.1 | ||
+ | ... */ | ||
+ | </code> | ||
+ | |||
+ | ===== Podsumowanie ===== | ||
+ | |||
+ | Algorytm **partial_sort** umożliwia wyodrębnienie **n** skrajnych elementów w danej kolekcji na podstawie pewnego kryterium, określonego za pomocą operatora mniejszości **operator<**, funkcji porównującej bądź funktora. Dzięki temu, nie trzeba sortować całej kolekcji, wystarczy sortowanie do momentu uzyskania żądanej ilości elementów, co skraca sam czas trwania operacji. | ||
+ | |||
+ | ===== Źródła ===== | ||
+ | |||
+ | Plik źródłowy z przykładami: {{:stl_algorytmy:partial_sort2.cpp}} | ||