DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK

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