На этом шаге мы рассмотрим алгоритмы, разбивающие коллекцию по некоторому критерию.
Для выполнения этой операции можно воспользоваться следующими алгоритмами:
void nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end) void nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end, BinaryPredncate op)
Обе формы сортируют элементы интервала [beg,end) так, чтобы элемент в позиции nth занимал правильное место в порядке сортировки, все предшествующие элементы были меньше либо равны этому элементу, а все последующие элементы - больше или равны ему. Таким образом, алгоритм создает два подинтервала, разделенных элементом в позиции nth, при этом любой элемент первого подинтервала меньше любого элемента второго подинтервала либо равен ему. Этого может быть достаточно, если вы хотите найти n старших или младших элементов без полной сортировки всего интервала.
Первая форма сортирует элементы оператором <.
Вторая форма сортирует элементы по критерию op(elem1,elem2).
Предикат ор не должен изменять свое состояние во время вызова.
Алгоритм partition() (смотри 301 шаг) тоже разбивает элементы интервала на две части по заданному критерию сортировки. Отличия между partition() и nth_element() описаны на 261 шаге.
Сложность в среднем линейная.
Пример использования алгоритма nth_element:
//--------------------------------------------------------------------------- #include <vcl.h> #include <iterator> #include "algostuff.hpp" #include <conio.h> //необходимо для getch() #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) { char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; } int main() { deque<int> coll; INSERT_ELEMENTS(coll,3,7); INSERT_ELEMENTS(coll,2,6); INSERT_ELEMENTS(coll,1,5); PRINT_ELEMENTS(coll,"Исходная коллекция:\n"); // Выделение четырех наименьших элементов nth_element (coll.begin(), // Начало интервала coll.begin()+3, // Граничный элемент coll.end()); // Конец интервала // Вывод cout << ToRus("Четыре наибольших элемента: "); copy (coll.begin(), coll.begin()+4, ostream_iterator<int>(cout," ")); cout << endl; // Выделение четырех наибольших элементов nth_element (coll.begin(), // Начало интервала coll.end()-4, // Граничный элемент coll.end()); // Конец интервала // Вывод cout << ToRus("Четыре наибольших элемента: "); copy (coll.end()-4, coll.end(), ostream_iterator<int>(cout," ")); cout << endl; // Выделение четырех наибольших элементов (второй вариант) nth_element (coll.begin(), // Начало интервала coll.begin()+3, // Граничный элемент coll.end(), // Конец интервала greater<int>()); // Критерий сортировки // Вывод cout << ToRus("Четыре наибольших элемента: "); copy (coll.begin(), coll.begin()+4, ostream_iterator<int>(cout," ")); cout << endl; getch(); return 0; } //---------------------------------------------------------------------------
Результат выполнения программы выглядит так:
Рис.1. Результат работы приложения
На следующем шаге мы рассмотрим сортировку в куче.
