.\" ident	@(#)Array_alg:man/select.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3select\fP \f3Array_alg(3C++)\fP " "
.SH NAME
select \- find the n smallest elements in an array
.SH SYNOPSIS OF Array_alg.h
.Bf
#include <stddef.h>

    template <class \*(gt>
    void select(ptrdiff_t n,\*(gt* b,\*(gt* e);
    template <class \*(gt>
    void select_r(int (*rel)(const \*(gt*,const \*(gt*),ptrdiff_t n,\*(gt* b,\*(gt* e);

.Be
.SH ASSUMPTIONS
.PP
(1) For the plain version, \f4\*(gt::operator<\f1
defines a total ordering relation on \*(gt
.br
(2) For the relational version, \f4rel\f1 
defines a total ordering relation on \*(gt
.br
(3) \*(gt has \f4operator=\f1
.SH DESCRIPTION
.PP
These functions place the nth smallest element of an array
into location \f4b+n\-1\f1. 
They also move the first \f4n\-1\f1 smallest elements to the
left of this location and the remaining elements to the 
right.  
.sp 0.5v
.IP "\f4template <class \*(gt>\f1"
.IC "\f4void select(ptrdiff_t n,\*(gt* b,\*(gt* e);\f1"
Uses \f4\*(gt::operator<\f1 to find
the nth smallest element.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4void select_r(int (*rel)(const \*(gt*,const \*(gt*),ptrdiff_t n,\*(gt* b,\*(gt* e);\f1"
.SH COMPLEXITY
.PP
If \f2N\f1 is the size of the array, 
then complexity is \f2O(N*N)\f1 in the worst case
and \f2O(N)\f1 on average.  The worst case is highly improbable.
If \f4n\f1 is less than \f21\f1 or greater than \f4e\-b\f1
then nothing is done.
.SH NOTES
These functions use \f3drand48(3C)\f1 to obtain
pseudo-random numbers.
.PP
Because a Block (see \f3Block(3C++)\f1)
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.
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3drand48(3C)\f1
\f3Block(3C++)\f1
.Be