zpr c++ quick reference

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== 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 << " ";

    /* 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 << " ";
</code>
zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
