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