Алгоритм partial_sort()

Алгоритм partial_sort()

template class RandomAccessIterator

void

partial_sort( RandomAccessIterator first,

RandomAccessIterator middle,

RandomAccessIterator last );

template

partial_sort() сортирует часть последовательности, укладывающуюся в диапазон [first,middle). Элементы в диапазоне [middle,last) остаются неотсортированными. Например, если дан массив

int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};

то вызов partial_sort(),где middle указывает на шестой элемент:

partial_sort( &ia[0], &ia[5], &ia[12] );

генерирует последовательность, в которой наименьшие пять (т.е. middle-first) элементов отсортированы:

{12,15,17,19,20,29,23,22,26,51,35,40}.

Элементы от middle до last-1 не расположены в каком-то определенном порядке, хотя значения каждого из них лежат вне отсортированной последовательности. В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция сравнения comp. Алгоритм partial_sort_copy()

template class InputIterator, class RandomAccessIterator

RandomAccessIterator

partial_sort_copy( InputIterator first, InputIterator last,

RandomAccessIterator result_first,

RandomAccessIterator result_last );

template class InputIterator, class RandomAccessIterator,

class Compare

RandomAccessIterator

partial_sort_copy( InputIterator first, InputIterator last,

RandomAccessIterator result_first,

RandomAccessIterator result_last,

Compare comp );

partial_sort_copy() ведет себя так же, как partial_sort(), только частично упорядоченная последовательность копируется в контейнер, ограниченный диапазоном [result_first,result_last] (если мы задаем отдельный контейнер для копирования результата, то в нем оказывается упорядоченная последовательность). Например, даны два массива:

int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};

int ia2[5];

Тогда обращение к partial_sort_copy(), где в качестве middle указан восьмой элемент:

partial_sort_copy( &ia[0], &ia[7], &ia[12],

&ia2[0], &ia2[5] );

заполняет массив ia2 пятью отсортированными элементами: {12,15,17,19,20}. Оставшиеся два элемента отсортированы не будут.

#include algorithm

#include vector

#include iostream.h

/*

* печатается:

исходный вектор: 69 23 80 42 17 15 26 51 19 12 35 8

результат применения partial_sort() к вектору: семь элементов

8 12 15 17 19 23 26 80 69 51 42 35

результат применения partial_sort_copy() к первым семи

элементам вектора в порядке убывания

26 23 19 17 15 12 8

*/

int main()

{

int ia[] = { 69,23,80,42,17,15,26,51,19,12,35,8 };

vector int,allocator vec( ia, ia+12 );

ostream_iteratorint out( cout," " );

cout "исходный вектор: ";

copy( vec.begin(), vec.end(), out ); cout endl;

cout "результат применения partial_sort() к вектору: "

"семь элементов ";

partial_sort( vec.begin(), vec.begin()+7, vec.end() );

copy( vec.begin(), vec.end(), out ); cout endl;

vector int, allocator res(7);

cout " результат применения partial_sort_copy() к первым семи "

"элементам вектора в порядке убывания ";

partial_sort_copy( vec.begin(), vec.begin()+7, res.begin(),

res.end(), greaterint() );

copy( res.begin(), res.end(), out ); cout endl;

}