Różnice

Różnice między wybraną wersją a wersją aktualną.

--- partial_sort [2008/12/12 12:24]
alaskow1
+++ partial_sort [2008/12/12 13:50] (aktualna)
alaskow1
@@ Linia 34: / Linia 34: @@
 ===== 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.
@@ Linia 42: / Linia 42: @@
 Do sortowania elementów wykorzystano algorytm **heapsort**, więc jego złożoność można oszacować wg poniższego wzoru:
-<code latex>O = (last - start)\cdot log(middle - start)</code>
+<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}}
+----
+//[[alaskow1@stud.elka.pw.edu.pl|Artur Marcin Laskowski]] 2008/12/12 13:48//

zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony