przejście do zawartości
zpr c++ quick reference
Narzędzia użytkownika
Zarejestruj się!
Zaloguj
Narzędzia witryny
Narzędzia
Pokaż stronę
Poprzednie wersje
Odnośniki
Ostatnie zmiany
Menadżer multimediów
Indeks
Zaloguj
Zarejestruj się!
Ostatnie zmiany
Menadżer multimediów
Indeks
Ślad:
partial_sort
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 << " "; //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 i następnych przykładach 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; } </code>
partial_sort.1229082317.txt.gz
· ostatnio zmienione: 2008/12/12 12:45 przez
alaskow1
Narzędzia strony
Pokaż stronę
Poprzednie wersje
Odnośniki
Do góry