C++ для начинающих

nth_element() переупорядочивает последовательность, ограниченную диапазоном [first,last), так что все элементы, меньшие чем тот, на который указывает итератор nth, оказываются перед ним, а все большие элементы - после. Например, если есть массив

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

то вызов nth_element(), в котором nth указывает на седьмой элемент (его значение равно 26):

nth_element( &ia[0], &ia[6], &ia[2] );

генерирует последовательность, в которой семь элементов, меньших 26, оказываются слева от 26, а четыре элемента, больших 26, справа:

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

При этом не гарантируется, что элементы, расположенные по обе стороны от nth, упорядочены. В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, во втором - бинарная операция сравнения, заданная программистом.

#include algorithm

#include vector

#include iostream.h

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

исходный вектор: 29 23 20 22 17 15 26 51 19 12 35 40

вектор, отсортированный относительно элемента 26

12 15 17 19 20 22 23 26 51 29 35 40

вектор, отсортированный по убыванию относительно элемента 23

40 35 29 51 26 23 22 20 19 17 15 12

*/

int main()

{

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

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

ostream_iteratorint out( cout," " );

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

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

cout "вектор, отсортированный относительно элемента "

*( vec.begin()+6 ) endl;

nth_element( vec.begin(), vec.begin()+6, vec.end() );

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

cout " вектор, отсортированный по убыванию "

"относительно элемента "

*( vec.begin()+6 ) endl;

nth_element( vec.begin(), vec.begin()+6,

vec.end(), greaterint() );

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

}

Алгоритм 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,