====== Algorytm partial_sort ======

===== Plik nagłówkowy =====

<code cpp>
#include    <algorithm>
</code>

===== Deklaracja funkcji =====

<code cpp>
template<class RandomAccessIterator>
    void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
    void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
</code>

===== Parametry funkcji =====

  * <code cpp>RandomAccessIterator first</code>
    Iterator wskazujący na początek zakresu częściowego sortowania w kolekcji.
  * <code cpp>RandomAccessIterator middle</code>
    Iterator wskazujący, ile elementów przed nim ma być posortowane.
  * <code cpp>RandomAccessIterator last</code>
    Iterator wskazujący na koniec zakresu częściowego sortowania w kolekcji.
  * <code cpp>Compare comp</code>
    Zewnętrzna funkcja lub funktor, służąca do porównywania elementów w kolekcji.

===== Wartość zwracana =====

Brak.

===== 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.

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

Do sortowania elementów wykorzystano algorytm **heapsort**, więc jego złożoność można oszacować wg poniższego wzoru:

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