1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
<html lang="en">
<head>
<title>Selecting the k smallest or largest elements - GNU Scientific Library -- Reference Manual</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="GNU Scientific Library -- Reference Manual">
<meta name="generator" content="makeinfo 4.8">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Sorting.html" title="Sorting">
<link rel="prev" href="Sorting-vectors.html" title="Sorting vectors">
<link rel="next" href="Computing-the-rank.html" title="Computing the rank">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with the
Invariant Sections being ``GNU General Public License'' and ``Free Software
Needs Free Documentation'', the Front-Cover text being ``A GNU Manual'',
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled ``GNU Free Documentation
License''.
(a) The Back-Cover Text is: ``You have freedom to copy and modify this
GNU Manual, like GNU software.''-->
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
--></style>
</head>
<body>
<div class="node">
<p>
<a name="Selecting-the-k-smallest-or-largest-elements"></a>
Next: <a rel="next" accesskey="n" href="Computing-the-rank.html">Computing the rank</a>,
Previous: <a rel="previous" accesskey="p" href="Sorting-vectors.html">Sorting vectors</a>,
Up: <a rel="up" accesskey="u" href="Sorting.html">Sorting</a>
<hr>
</div>
<h3 class="section">11.3 Selecting the k smallest or largest elements</h3>
<p>The functions described in this section select the k smallest
or largest elements of a data set of size N. The routines use an
O(kN) direct insertion algorithm which is suited to subsets that
are small compared with the total size of the dataset. For example, the
routines are useful for selecting the 10 largest values from one million
data points, but not for selecting the largest 100,000 values. If the
subset is a significant part of the total dataset it may be faster
to sort all the elements of the dataset directly with an O(N \log
N) algorithm and obtain the smallest or largest values that way.
<div class="defun">
— Function: int <b>gsl_sort_smallest</b> (<var>double * dest, size_t k, const double * src, size_t stride, size_t n</var>)<var><a name="index-gsl_005fsort_005fsmallest-1063"></a></var><br>
<blockquote><p>This function copies the <var>k</var> smallest elements of the array
<var>src</var>, of size <var>n</var> and stride <var>stride</var>, in ascending
numerical order into the array <var>dest</var>. The size <var>k</var> of the subset must be
less than or equal to <var>n</var>. The data <var>src</var> is not modified by
this operation.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_sort_largest</b> (<var>double * dest, size_t k, const double * src, size_t stride, size_t n</var>)<var><a name="index-gsl_005fsort_005flargest-1064"></a></var><br>
<blockquote><p>This function copies the <var>k</var> largest elements of the array
<var>src</var>, of size <var>n</var> and stride <var>stride</var>, in descending
numerical order into the array <var>dest</var>. <var>k</var> must be
less than or equal to <var>n</var>. The data <var>src</var> is not modified by
this operation.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_sort_vector_smallest</b> (<var>double * dest, size_t k, const gsl_vector * v</var>)<var><a name="index-gsl_005fsort_005fvector_005fsmallest-1065"></a></var><br>
— Function: int <b>gsl_sort_vector_largest</b> (<var>double * dest, size_t k, const gsl_vector * v</var>)<var><a name="index-gsl_005fsort_005fvector_005flargest-1066"></a></var><br>
<blockquote><p>These functions copy the <var>k</var> smallest or largest elements of the
vector <var>v</var> into the array <var>dest</var>. <var>k</var>
must be less than or equal to the length of the vector <var>v</var>.
</p></blockquote></div>
<p>The following functions find the indices of the k smallest or
largest elements of a dataset,
<div class="defun">
— Function: int <b>gsl_sort_smallest_index</b> (<var>size_t * p, size_t k, const double * src, size_t stride, size_t n</var>)<var><a name="index-gsl_005fsort_005fsmallest_005findex-1067"></a></var><br>
<blockquote><p>This function stores the indices of the <var>k</var> smallest elements of
the array <var>src</var>, of size <var>n</var> and stride <var>stride</var>, in the
array <var>p</var>. The indices are chosen so that the corresponding data is
in ascending numerical order. <var>k</var> must be
less than or equal to <var>n</var>. The data <var>src</var> is not modified by
this operation.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_sort_largest_index</b> (<var>size_t * p, size_t k, const double * src, size_t stride, size_t n</var>)<var><a name="index-gsl_005fsort_005flargest_005findex-1068"></a></var><br>
<blockquote><p>This function stores the indices of the <var>k</var> largest elements of
the array <var>src</var>, of size <var>n</var> and stride <var>stride</var>, in the
array <var>p</var>. The indices are chosen so that the corresponding data is
in descending numerical order. <var>k</var> must be
less than or equal to <var>n</var>. The data <var>src</var> is not modified by
this operation.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_sort_vector_smallest_index</b> (<var>size_t * p, size_t k, const gsl_vector * v</var>)<var><a name="index-gsl_005fsort_005fvector_005fsmallest_005findex-1069"></a></var><br>
— Function: int <b>gsl_sort_vector_largest_index</b> (<var>size_t * p, size_t k, const gsl_vector * v</var>)<var><a name="index-gsl_005fsort_005fvector_005flargest_005findex-1070"></a></var><br>
<blockquote><p>These functions store the indices of the <var>k</var> smallest or largest
elements of the vector <var>v</var> in the array <var>p</var>. <var>k</var> must be less than or equal to the length of the vector
<var>v</var>.
</p></blockquote></div>
<hr>The GNU Scientific Library - a free numerical library licensed under the GNU GPL<br>Back to the <a href="/software/gsl/">GNU Scientific Library Homepage</a></body></html>
|
