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