Narzędzia użytkownika
partial_sort
Różnice
Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
partial_sort [2008/12/12 12:55] alaskow1 |
partial_sort [2008/12/12 13:50] (aktualna) 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 mniejszości 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. | ||
| Linia 71: | Linia 71: | ||
| cout << *iter << " "; | cout << *iter << " "; | ||
| - | //out: 23 16 54 21 14 38 63 29 | + | /* out: 23 16 54 21 14 38 63 29 */ |
| /* Sortowanie kolekcji, do uzyskania 4 posortowanych elementów */ | /* Sortowanie kolekcji, do uzyskania 4 posortowanych elementów */ | ||
| Linia 82: | Linia 82: | ||
| cout << *iter << " "; | cout << *iter << " "; | ||
| - | //out: 14 16 21 23 54 38 63 29 | + | /* out: 14 16 21 23 54 38 63 29 */ |
| </code> | </code> | ||
| Linia 183: | Linia 183: | ||
| === Sortowanie wg wbudowanego operatora mniejszości === | === Sortowanie wg wbudowanego operatora mniejszości === | ||
| - | Tu sortowanie odbywa się przy użyciu wbudowanego operatora mniejszości, który przy obecnym ustawieniu sortuje karty alfabetycznie. Chcemy zatem uzyskać trzy pierwsze karty: | + | 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> | <code cpp> | ||
| partial_sort(second.begin(), second.begin() + 3, second.end()); | 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> | </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}} | ||
| + | |||
| + | |||
| + | ---- | ||
| + | //[[alaskow1@stud.elka.pw.edu.pl|Artur Marcin Laskowski]] 2008/12/12 13:48// | ||
partial_sort.1229082947.txt.gz · ostatnio zmienione: 2008/12/12 12:55 przez alaskow1
Narzędzia strony
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji: CC Attribution-Noncommercial-Share Alike 3.0 Unported
