# select(3C++)

**select --
find the n smallest elements in an array
**

## Synopsis

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);

## Assumptions

(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=**.

## Description

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.

## Complexity

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.

## Notes

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.

## References

**Array_alg**(3C++),
**Block**(3C++),
**drand48**(3C)

*
© 2004 The SCO Group, Inc. All rights reserved.
*

UnixWare 7 Release 7.1.4 - 25 April 2004