На этом шаге мы рассмотрим алгоритмы, выполняющие простую частичную сортировку.
Для выполнения простой частичной сортировки можно воспользоваться следующими алгоритмами:
void partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end) void partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end, BinaryPredicate op)
Первая форма сортирует элементы интервала [beg,end) оператором < так, чтобы интервал [beg,sortEnd) содержал упорядоченные элементы.
Вторая форма сортирует элементы по критерию op(elem1,elem2) так, чтобы интервал [beg,sortEnd) содержал упорядоченные элементы.
Предикат ор не должен изменять свое состояние во время вызова.
В отличие от sort() алгоритм partial_sort() сортирует не все элементы интервала, а прекращает сортировку после того, как подинтервал от начала до sortEnd будет заполнен упорядоченными элементами. Например, если после сортировки интервала вам понадобятся только первые три элемента, этот алгоритм работает более эффективно, поскольку он не тратит время на сортировку остальных элементов.
Если sortEnd совпадает с end, алгоритм partial_sort() сортирует весь интервал, В среднем по сложности он уступает sort(), но в худшем случае обеспечивает более высокое быстродействие (смотри сравнительный анализ алгоритмов сортировки на 260 шаге).
Сложность от линейной до n*log(n) (примерно numberOfElements*log(numberOfSortedElements) сравнений).
Пример использования алгоритма partial_sort():
//--------------------------------------------------------------------------- #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"); // Сортировка первых пяти элементов partial_sort (coll.begin(), // Начало интервала coll.begin()+5, // Конец упорядоченного интервала coll.end()); // Конец всего интервала PRINT_ELEMENTS(coll,"Сортировка первых пяти элементов:\n"); // Сортировка первых пяти элементов в обратном порядке partial_sort (coll.begin(), // Начало интервала coll.begin()+5, // Конец упорядоченного интервала coll.end(), // Конец всего интервала greater<int>()); // Критерий сортировки PRINT_ELEMENTS(coll,"Сортировка первых пяти элементов в обратном порядке:\n"); // Сортировка всех элементов partial_sort (coll.begin(), // Начало интервала coll.end(), // Конец упорядоченного интервала coll.end()); // Конец всего интервала PRINT_ELEMENTS(coll,"Сортировка всех элементов:\n"); getch(); return 0; } //---------------------------------------------------------------------------
Результат выполнения программы выглядит так:
Рис.1. Результат работы приложения
На следующем шаге мы рассмотрим частичную сортировку с копированием.
