|
|
template <class T>
void select(ptrdiff_t n,T* b,T* e);
template <class T>
void select_r(int (*rel)(const T*,const T*),
ptrdiff_t n,T* b,T* e);
(1) For the plain version, T::operator< defines a total ordering relation on T.
(2) For the relational version, rel defines a total ordering relation on T.
(3) T has operator=.
These functions place the nth smallest element of an array into location b+n-1. They also move the first n-1 smallest elements to the left of this location and the remaining elements to the right.
template <class T> void select(ptrdiff_t n,T* b,T* e);
Uses T::operator< to find the nth smallest element.
template <class T>
void select_r(int (*rel)(const T*,const T*),
ptrdiff_t n,T* b,T* e);
Uses rel to find the nth smallest element.
If N is the size of the array, then complexity is O(N*N) in the worst case and O(N) on average. The worst case is highly improbable. If n is less than 1 or greater than e-b then nothing is done.
These functions use drand48(3C) to obtain pseudo-random numbers.
Because a Block (see Block(3C++)) can always be used wherever an array is called for, Array Algorithms can also be used with Blocks. In fact, these two components were actually designed to be used together.