File: Selecting-the-k-smallest-or-largest-elements.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (150 lines) | stat: -rw-r--r-- 8,767 bytes parent folder | download
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 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.3 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 the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: Selecting the k smallest or largest elements</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Selecting the k smallest or largest elements">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Selecting the k smallest or largest elements">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Sorting.html#Sorting" rel="up" title="Sorting">
<link href="Computing-the-rank.html#Computing-the-rank" rel="next" title="Computing the rank">
<link href="Sorting-vectors.html#Sorting-vectors" rel="previous" title="Sorting vectors">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Selecting-the-k-smallest-or-largest-elements"></a>
<div class="header">
<p>
Next: <a href="Computing-the-rank.html#Computing-the-rank" accesskey="n" rel="next">Computing the rank</a>, Previous: <a href="Sorting-vectors.html#Sorting-vectors" accesskey="p" rel="previous">Sorting vectors</a>, Up: <a href="Sorting.html#Sorting" accesskey="u" rel="up">Sorting</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Selecting-the-k-smallest-or-largest-elements-1"></a>
<h3 class="section">12.3 Selecting the k smallest or largest elements</h3>

<p>The functions described in this section select the <em>k</em> smallest
or largest elements of a data set of size <em>N</em>.  The routines use an
<em>O(kN)</em> 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 <em>O(N \log
N)</em> algorithm and obtain the smallest or largest values that way.
</p>
<dl>
<dt><a name="index-gsl_005fsort_005fsmallest"></a>Function: <em>int</em> <strong>gsl_sort_smallest</strong> <em>(double * <var>dest</var>, size_t <var>k</var>, const double * <var>src</var>, size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dd><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></dd></dl>

<dl>
<dt><a name="index-gsl_005fsort_005flargest"></a>Function: <em>int</em> <strong>gsl_sort_largest</strong> <em>(double * <var>dest</var>, size_t <var>k</var>, const double * <var>src</var>, size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dd><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></dd></dl>

<dl>
<dt><a name="index-gsl_005fsort_005fvector_005fsmallest"></a>Function: <em>int</em> <strong>gsl_sort_vector_smallest</strong> <em>(double * <var>dest</var>, size_t <var>k</var>, const gsl_vector * <var>v</var>)</em></dt>
<dt><a name="index-gsl_005fsort_005fvector_005flargest"></a>Function: <em>int</em> <strong>gsl_sort_vector_largest</strong> <em>(double * <var>dest</var>, size_t <var>k</var>, const gsl_vector * <var>v</var>)</em></dt>
<dd><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></dd></dl>

<p>The following functions find the indices of the <em>k</em> smallest or
largest elements of a dataset,
</p>
<dl>
<dt><a name="index-gsl_005fsort_005fsmallest_005findex"></a>Function: <em>int</em> <strong>gsl_sort_smallest_index</strong> <em>(size_t * <var>p</var>, size_t <var>k</var>, const double * <var>src</var>, size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dd><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></dd></dl>

<dl>
<dt><a name="index-gsl_005fsort_005flargest_005findex"></a>Function: <em>int</em> <strong>gsl_sort_largest_index</strong> <em>(size_t * <var>p</var>, size_t <var>k</var>, const double * <var>src</var>, size_t <var>stride</var>, size_t <var>n</var>)</em></dt>
<dd><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></dd></dl>

<dl>
<dt><a name="index-gsl_005fsort_005fvector_005fsmallest_005findex"></a>Function: <em>int</em> <strong>gsl_sort_vector_smallest_index</strong> <em>(size_t * <var>p</var>, size_t <var>k</var>, const gsl_vector * <var>v</var>)</em></dt>
<dt><a name="index-gsl_005fsort_005fvector_005flargest_005findex"></a>Function: <em>int</em> <strong>gsl_sort_vector_largest_index</strong> <em>(size_t * <var>p</var>, size_t <var>k</var>, const gsl_vector * <var>v</var>)</em></dt>
<dd><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></dd></dl>


<hr>
<div class="header">
<p>
Next: <a href="Computing-the-rank.html#Computing-the-rank" accesskey="n" rel="next">Computing the rank</a>, Previous: <a href="Sorting-vectors.html#Sorting-vectors" accesskey="p" rel="previous">Sorting vectors</a>, Up: <a href="Sorting.html#Sorting" accesskey="u" rel="up">Sorting</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>