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
151
152
153
154
155
156
|
<!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 – Reference Manual: Sorting objects</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Sorting objects">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Sorting objects">
<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="Sorting-vectors.html#Sorting-vectors" rel="next" title="Sorting vectors">
<link href="Sorting.html#Sorting" rel="previous" title="Sorting">
<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="Sorting-objects"></a>
<div class="header">
<p>
Next: <a href="Sorting-vectors.html#Sorting-vectors" accesskey="n" rel="next">Sorting vectors</a>, Up: <a href="Sorting.html#Sorting" accesskey="u" rel="up">Sorting</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Sorting-objects-1"></a>
<h3 class="section">12.1 Sorting objects</h3>
<p>The following function provides a simple alternative to the standard
library function <code>qsort</code>. It is intended for systems lacking
<code>qsort</code>, not as a replacement for it. The function <code>qsort</code>
should be used whenever possible, as it will be faster and can provide
stable ordering of equal elements. Documentation for <code>qsort</code> is
available in the <cite>GNU C Library Reference Manual</cite>.
</p>
<p>The functions described in this section are defined in the header file
<samp>gsl_heapsort.h</samp>.
</p>
<a name="index-comparison-functions_002c-definition"></a>
<dl>
<dt><a name="index-gsl_005fheapsort"></a>Function: <em>void</em> <strong>gsl_heapsort</strong> <em>(void * <var>array</var>, size_t <var>count</var>, size_t <var>size</var>, gsl_comparison_fn_t <var>compare</var>)</em></dt>
<dd>
<p>This function sorts the <var>count</var> elements of the array <var>array</var>,
each of size <var>size</var>, into ascending order using the comparison
function <var>compare</var>. The type of the comparison function is defined by,
</p>
<div class="example">
<pre class="example">int (*gsl_comparison_fn_t) (const void * a,
const void * b)
</pre></div>
<p>A comparison function should return a negative integer if the first
argument is less than the second argument, <code>0</code> if the two arguments
are equal and a positive integer if the first argument is greater than
the second argument.
</p>
<p>For example, the following function can be used to sort doubles into
ascending numerical order.
</p>
<div class="example">
<pre class="example">int
compare_doubles (const double * a,
const double * b)
{
if (*a > *b)
return 1;
else if (*a < *b)
return -1;
else
return 0;
}
</pre></div>
<p>The appropriate function call to perform the sort is,
</p>
<div class="example">
<pre class="example">gsl_heapsort (array, count, sizeof(double),
compare_doubles);
</pre></div>
<p>Note that unlike <code>qsort</code> the heapsort algorithm cannot be made into
a stable sort by pointer arithmetic. The trick of comparing pointers for
equal elements in the comparison function does not work for the heapsort
algorithm. The heapsort algorithm performs an internal rearrangement of
the data which destroys its initial ordering.
</p></dd></dl>
<a name="index-indirect-sorting"></a>
<dl>
<dt><a name="index-gsl_005fheapsort_005findex"></a>Function: <em>int</em> <strong>gsl_heapsort_index</strong> <em>(size_t * <var>p</var>, const void * <var>array</var>, size_t <var>count</var>, size_t <var>size</var>, gsl_comparison_fn_t <var>compare</var>)</em></dt>
<dd>
<p>This function indirectly sorts the <var>count</var> elements of the array
<var>array</var>, each of size <var>size</var>, into ascending order using the
comparison function <var>compare</var>. The resulting permutation is stored
in <var>p</var>, an array of length <var>n</var>. The elements of <var>p</var> give the
index of the array element which would have been stored in that position
if the array had been sorted in place. The first element of <var>p</var>
gives the index of the least element in <var>array</var>, and the last
element of <var>p</var> gives the index of the greatest element in
<var>array</var>. The array itself is not changed.
</p></dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Sorting-vectors.html#Sorting-vectors" accesskey="n" rel="next">Sorting vectors</a>, Up: <a href="Sorting.html#Sorting" accesskey="u" rel="up">Sorting</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
