622064ba2cdf63e29325a4877750f9377f6e1176
[scilab.git] / scilab / modules / elementary_functions / help / en_US / searchandsort / gsort.xml
1 <?xml version="1.0" encoding="UTF-8"?>
2 <!--
3  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
4  * Copyright (C) 2008 - INRIA
5  *
6  * Copyright (C) 2012 - 2016 - Scilab Enterprises
7  *
8  * This file is hereby licensed under the terms of the GNU GPL v2.0,
9  * pursuant to article 5.3.4 of the CeCILL v.2.1.
10  * This file was originally licensed under the terms of the CeCILL v2.1,
11  * and continues to be available under such terms.
12  * For more information, see the COPYING file which you should have received
13  * along with this program.
14  *
15  -->
16 <refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg" xmlns:ns5="http://www.w3.org/1999/xhtml" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook" xmlns:scilab="http://www.scilab.org" xml:id="gsort" xml:lang="en">
17     <refnamediv>
18         <refname>gsort</refname>
19         <refpurpose>sorting by quick sort algorithm</refpurpose>
20     </refnamediv>
21     <refsynopsisdiv>
22         <title>Syntax</title>
23         <synopsis>[B [,k]]=gsort(A)
24             [B [,k]]=gsort(A,option)
25             [B [,k]]=gsort(A,option,direction)
26         </synopsis>
27     </refsynopsisdiv>
28     <refsection>
29         <title>Arguments</title>
30         <variablelist>
31             <varlistentry>
32                 <term>A</term>
33                 <listitem>
34                     <para>
35                         scalar, vector, matrix or hypermatrix of booleans, integers, real numbers,
36                         or text, or a sparse vector of reals.
37                     </para>
38                 </listitem>
39             </varlistentry>
40             <varlistentry>
41                 <term>option</term>
42                 <listitem>
43                     <para>a character string. It gives the type of sort to
44                         perform:
45                     </para>
46                     <itemizedlist>
47                         <listitem>
48                             <para>
49                                 'r' : each column of <literal>A</literal> is sorted
50                             </para>
51                         </listitem>
52                         <listitem>
53                             <para>
54                                 'c': each row of <literal>A</literal> is sorted
55                             </para>
56                         </listitem>
57                         <listitem>
58                             <para>
59                                 'g': all elements of <literal>A</literal> are sorted. It
60                                 is the default value.
61                             </para>
62                         </listitem>
63                         <listitem>
64                             <para>'lr': lexicographic sort of the rows of
65                                 <literal>A</literal>
66                             </para>
67                         </listitem>
68                         <listitem>
69                             <para>'lc': lexicographic sort of the columns of
70                                 <literal>A</literal>
71                             </para>
72                         </listitem>
73                     </itemizedlist>
74                 </listitem>
75             </varlistentry>
76             <varlistentry>
77                 <term>direction</term>
78                 <listitem>
79                     <para>a character string. It gives the ordering direction:
80                         <literal>'i'</literal> stand for increasing and
81                         <literal>'d'</literal> for decreasing order (default).
82                     </para>
83                 </listitem>
84             </varlistentry>
85             <varlistentry>
86                 <term>B</term>
87                 <listitem>
88                     <para>an array with same type and dimensions as
89                         <literal>A</literal>.
90                     </para>
91                 </listitem>
92             </varlistentry>
93             <varlistentry>
94                 <term>k</term>
95                 <listitem>
96                     <para>a real array with integer values and same dimensions as
97                         <literal>A</literal>. Contains the origin indices.
98                     </para>
99                 </listitem>
100             </varlistentry>
101         </variablelist>
102     </refsection>
103     <refsection>
104         <title>Description</title>
105         <para>
106             <literal>gsort</literal> implements a "quick sort" algorithm for
107             various data types.
108         </para>
109         <itemizedlist>
110             <listitem>
111                 <para>
112                     <literal>B=gsort(A,'g')</literal>,
113                     <literal>B=gsort(A,'g','d')</literal> and
114                     <literal>B=gsort(A)</literal> sort the elements of the array
115                     <literal>A</literal>, seen as <literal>A(:)</literal> in a decreasing
116                     order.
117                 </para>
118                 <para>
119                     <literal>B=gsort(A,'g','i')</literal> sort the elements of the
120                     array <literal>A</literal> in the increasing order.
121                 </para>
122             </listitem>
123             <listitem>
124                 <para>
125                     <literal>B=gsort(A,'lr')</literal> sorts the rows of
126                     <literal>A</literal> in lexical decreasing order. <literal>B</literal>
127                     is obtained by a permutation of the rows of matrix
128                     <literal>A</literal> in such a way that the rows of
129                     <literal>B</literal> verify <literal>B(i,:)&gt;=B(j,:)</literal> if
130                     <literal>i&lt;j</literal>.
131                 </para>
132                 <para>
133                     <literal>B=gsort(A,'lr','i')</literal> works similarly for
134                     increasing lexical order.
135                 </para>
136             </listitem>
137             <listitem>
138                 <para>
139                     <literal>B=gsort(A,'lc')</literal> sorts the columns of
140                     <literal>A</literal> in lexical decreasing order. <literal>B</literal>
141                     is obtained by a permutation of the columns of matrix
142                     <literal>A</literal> in such a way that the columns of
143                     <literal>B</literal> verify <literal>B(:,i)&gt;=B(:,j)</literal> if
144                     <literal>i&lt;j</literal>.
145                 </para>
146                 <para>
147                     <literal>B=gsort(A,'lc','i')</literal> works similarly for
148                     increasing lexical order.
149                 </para>
150             </listitem>
151         </itemizedlist>
152         <para>
153             If required the second return argument <literal>k</literal> contains
154             the indices of the sorted values in <literal>A</literal>. If
155             <literal>[B,k]=gsort(A,'g')</literal> one has <literal>B==A(k)</literal>.
156             <emphasis role="bold">The algorithm preserve the relative order of
157                 records with equal values.
158             </emphasis>
159         </para>
160         <para>
161             When <literal>v</literal> is complex, the elements are sorted by
162             magnitude, i.e., abs(<literal>v</literal>) .
163         </para>
164         <para>
165             With complex numbers, <literal>gsort</literal> can be overloaded
166         </para>
167         <para>Create macro:
168             SCI/modules/elementary_functions/macros/%_gsort.sci
169         </para>
170         <para>Overloading for not managed type (others than a real, an integer or a character
171             string vector/matrix or a sparse vector.) is allowed.
172         </para>
173         <para>
174             if <literal>v</literal> have <literal>%nan</literal> or
175             <literal>%inf</literal> as elements. gsort places these at the beginning
176             with <literal>'d'</literal> or at the end with <literal>'i'</literal>
177             argument.
178         </para>
179     </refsection>
180     <refsection>
181         <title>Examples</title>
182         <programlisting role="example">
183             alr=[1,2,2;
184             1,2,1;
185             1,1,2;
186             1,1,1];
187             [alr1,k]=gsort(alr,'lr','i')
188             [alr1,k]=gsort(alr,'lc','i')
189
190             v=int32(alr)
191
192             gsort(v)
193             gsort(v,'lr','i')
194             gsort(v,'lc','i')
195
196             v=['Scilab' '2.6'
197             'Scilab' '2.7'
198             'xcos' '2.7'
199             'Scilab' '3.1'
200             'xcos' '3.1'
201             'xcos' '4.0'
202             'Scilab' '4.0']
203
204             gsort(v,'lr','i')
205             gsort(v,'lc','i')
206         </programlisting>
207     </refsection>
208     <refsection role="see also">
209         <title>See also</title>
210         <simplelist type="inline">
211             <member>
212                 <link linkend="find">find</link>
213             </member>
214             <member>
215                 <link linkend="overloading">overloading</link>
216             </member>
217         </simplelist>
218     </refsection>
219     <refsection>
220         <title>Bibliography</title>
221         <para>Quick sort algorithm from Bentley &amp; McIlroy's "Engineering a
222             Sort Function". Software---Practice and Experience,
223             23(11):1249-1265
224         </para>
225     </refsection>
226     <refsection>
227         <title>History</title>
228         <revhistory>
229             <revision>
230                 <revnumber>5.4.0</revnumber>
231                 <revremark>This function allows overloading for unmanaged type (others than a real, an integer or a character string vector/matrix or a sparse vector).</revremark>
232             </revision>
233             <revision>
234                 <revnumber>6.1.0</revnumber>
235                 <revremark>
236                     Booleans can now be sorted.
237                 </revremark>
238             </revision>
239         </revhistory>
240     </refsection>
241 </refentry>