1 <?xml version="1.0" encoding="UTF-8"?>
3 * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
4 * Copyright (C) 2008 - INRIA
5 * Copyright (C) 2012 - 2016 - Scilab Enterprises
6 * Copyright (C) 2018 - 2020 - Samuel GOUGEON
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.
16 <refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink"
17 xmlns:svg="http://www.w3.org/2000/svg" xmlns:ns5="http://www.w3.org/1999/xhtml"
18 xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook"
19 xmlns:scilab="http://www.scilab.org" xml:id="gsort" xml:lang="en">
21 <refname>gsort</refname>
22 <refpurpose>sorting by quick sort algorithm</refpurpose>
29 B = gsort(A, method, direction)
30 B = gsort(A, method, directions, rankFuncs)
35 <title>Arguments</title>
40 Scalar, vector, matrix or hypermatrix of booleans, integers, real or complex
41 numbers, or text, or a sparse vector of real numbers.
43 Overloading for unhandled types is allowed.
51 A keyword: The sorting method:
54 <th>'g'</th><td>:</td>
55 <td>General sorting: All elements of <literal>A</literal> are sorted
60 <th>'r'</th><td>:</td>
61 <td>Rows of each column of <literal>A</literal> are sorted.</td>
64 <th>'c'</th><td>:</td>
65 <td>Columns of each row of <literal>A</literal> are sorted.</td>
67 <tr valign="top"><th>'lr'</th><td>:</td>
68 <td>lexicographic sort of the rows of <literal>A</literal>:
69 Sorts rows according to values in the first column. If a group of
70 sorted rows have the same value in column #1, resorts the group
71 according to values in column #2. etc.
72 Not applicable to hypermatrices.
75 <tr valign="top"><th>'lc'</th><td>:</td>
76 <td>lexicographic sort of the columns of <literal>A</literal>
77 (not for hypermatrices).
85 <term>direction</term>
87 "d" for <emphasis role="bold">d</emphasis>ecreasing order (default), or
88 "i" for <emphasis role="bold">i</emphasis>ncreasing one.
93 <term>directions</term>
95 vector of "i" and "d" characters, with as many elements than
96 <varname>rankFuncs</varname> has.
97 <literal>directions(k)</literal> is used for <varname>rankFuncs(k)</varname>.
102 <term>rankFuncs</term>
104 list() whose elements are among the following type:
107 identifier <literal>fun</literal> of a function in Scilab language
108 or of a builtin function.
111 : colon. It stands for a <literal>fun</literal> such that
112 <literal>fun(A)</literal> returns <literal>A</literal>.
115 a <literal>list(fun, param1, param2,..)</literal> where
118 <literal>fun</literal> is the identifier of a Scilab or
122 <literal>param1, param2,..</literal> are parameters.
125 such that <literal>fun(A, param1, param2, ..)</literal> will be called.
129 The functions <literal>fun</literal> must fullfill the following conditions:
132 <literal>R=fun(A)</literal> or <literal>R=fun(A, param1, param2,..)</literal>
136 <literal>fun</literal> must work in an element-wise way, meaning:
137 <literal>size(R)==size(A)</literal>, and <literal>R(k)</literal>
138 is about only <literal>A(k)</literal>
141 <literal>R</literal> must be of simple sortable type: boolean,
148 When <literal>A</literal> are complex numbers, the usual functions
149 <literal>real, imag, abs, atan</literal> can be specified. Then,
150 <literal>atan(imag(A),real(A))</literal> will be called instead of
151 <literal>atan(A)</literal>.
159 The sorted array, with <literal>A</literal>'s data type, encoding, and sizes.
166 Array of decimal integers, of size <literal>size(A)</literal>:
167 Initial indices of <literal>B</literal> elements, in <literal>A</literal>.
168 If <literal>A</literal> is a matrix, according to the chosen method,
171 <th valign="top">"g"</th><td>:</td>
173 <literal>k</literal> is a matrix of size(A): <literal>k(i)</literal>
175 of <literal>B(i)</literal> in <literal>A</literal>, such that
176 <literal>B(:) = A(k)</literal>.
180 <th valign="top">"r"</th><td>:</td>
182 <literal>k</literal> is a matrix of size(A): <literal>k(i,j)</literal>
183 is the <literal>1 ≤ index ≤ size(A,1)</literal>
184 of <literal>B(i,j)</literal> in the column <literal>A(:,j)</literal>.
188 <th valign="top">"c"</th><td>:</td>
190 <literal>k</literal> is a matrix of size(A): <literal>k(i,j)</literal>
191 is the <literal>1 ≤ index ≤ size(A,2)</literal>
192 of <literal>B(i,j)</literal> in the row <literal>A(i,:)</literal>.
196 <th valign="top">"lr"</th><td>:</td>
198 <literal>k</literal> is a column of size(A,1), such that
199 <literal>B = A(k,:)</literal>.
203 <th valign="top">"lc"</th><td>:</td>
205 <literal>k</literal> is a row of size(A,2), such that
206 <literal>B = A(:,k)</literal>.
216 <title>Description</title>
218 <literal>gsort</literal> performs a "quick sort" for various native data types.
219 By default, sorting is performed in decreasing order.
222 <literal>%nan</literal> values are considered greater than <literal>%inf</literal>.
225 Complex numbers are by default sorted only according to their moduli.
226 Complete sorting can be achieved using the multilevel mode, through the
227 <varname>rankFuncs</varname> and <varname>directions</varname> arguments.
231 <literal>M = gsort(C, "g", ["i" "d"], list(real, imag))</literal><para/>
232 will sort the array C, first by increasing real parts, and for elements
233 of equal real parts, second by decreasing imaginary parts.
234 The multilevel mode is described with details in a dedicated subsection below.
237 Texts are sorted in alphabetical order, in a case-sensitive way.
238 Extended UTF characters are supported.
242 Whatever is the chosen method, <emphasis role="bold">the algorithm preserves the
243 relative order of elements with equal values.
248 <title>Sorting methods</title>
250 <emphasis role="bold">B = gsort(A,'g', ..)</emphasis> sorts all elements of
251 <varname>A</varname>, and stores sorted elements in the first column from top to
252 bottom, then in the second column, etc.
255 <emphasis role="bold">B = gsort(A,'c', ..)</emphasis> sorts each row of A.
256 Each sorted element is on the same row as in A, but possibly on another column
257 corresponding to its sorting rank on the row.
260 <emphasis role="bold">B = gsort(A,'r', ..)</emphasis> sorts each column of A.
261 Each sorted element is on the same column as in A, but possibly on another row
262 corresponding to its sorting rank.
265 <emphasis role="bold">B = gsort(A,'lr', ..)</emphasis> sorts rows of A, as a whole,
266 in a lexical way. Two rows are compared and sorted in the following way:
267 The elements of their first column are compared. If their ranks are not equal,
268 both rows are sorted accordingly. Otherwise, the elements of their second column
269 are compared. etc... up to the last column if it is required.
272 <emphasis role="bold">B = gsort(A,'lc', ..)</emphasis> sorts columns of A,
273 as a whole, in a lexical way (see above).
277 <title>Multilevel sorting</title>
279 As noted above, when two compared elements have equal ranks, their initial relative
280 order in <literal>A</literal> is preserved in the result <literal>B</literal> .
283 However, in many cases, going beyond through a multi-level sorting can be useful
285 After the first sort performed according to a first criterion and sorting
286 direction, it is possible to define a second criterion and sorting
287 direction and apply them to 1st-rank-equal elements gathered by the first sort.
290 If after the two first sorting some elements have still the same ranks, it is
291 possible to define and use a 3rd sorting level, etc.
294 <emphasis role="bold">Applied examples</emphasis> (see also the Examples section):
297 <emphasis>Sorting a matrix C of complex numbers,
298 first: by increasing modulus, second: by increasing phase</emphasis>:
300 <literal>gsort(C, "g", ["i" "i"], list(abs, atan))</literal>
304 <emphasis>Sorting the columns of a matrix T of texts,
305 first: by increasing length, second: in anti-alphabetical order</emphasis>:
307 <literal>gsort(T, "c", ["i" "d"], list(length, :))</literal>
311 <emphasis>Sorting a matrix P of polynomials,
312 first: by increasing degree, second: by decreasing value of the constant
313 0-degree coefficient</emphasis>:
315 function c = get_coef(p, i)
316 // i: degree of the coeff to return
317 c = matrix(coeff(p(:))(:,i+1), size(p))
320 gsort(P, "c", ["i" "d"], list(degree, list(get_coef,0)))
322 In this example, the second ranking function allows to specify the degree i
323 of the coefficient to be considered as secondary sorting value.
327 <emphasis>Sorting a matrix D of decimal numbers,
328 first: by increasing integer parts, second: by decreasing fractional parts</emphasis>:
330 function r = get_frac(numbers)
331 r = numbers - int(numbers)
334 gsort(D, "g", ["i" "d"], list(int, get_frac))
343 <title>Examples</title>
345 Sorting elements in rows:
347 <programlisting role="example"><![CDATA[
348 m = [ 0. 2. 1. 2. 1. 0.
352 [s, k] = gsort(m, "c")
353 ]]> </programlisting>
355 --> [s, k] = gsort(m, "c")
368 Lexicographic sorting of rows:
370 <programlisting role="example"><![CDATA[
378 [s, k] = gsort(v,'lr','i'); s, k'
379 ]]> </programlisting>
381 --> [s, k] = gsort(v,'lr','i'); s, k'
396 Lexicographic sorting of columns:
398 <programlisting role="example"><![CDATA[
399 m = [ 0. 1. 0. 1. 1. 1. 0. 1.
400 0. 0. 1. 1. 1. 1. 0. 0.
401 0. 0. 1. 1. 0. 0. 0. 0.
404 [s, k] = gsort(m, "lc", "i") // sorting columns
405 ]]> </programlisting>
407 --> [s, k] = gsort(m, "lc", "i")
409 0. 0. 0. 1. 1. 1. 1. 1.
410 0. 0. 1. 0. 0. 1. 1. 1.
411 0. 0. 1. 0. 0. 0. 0. 1.
414 1. 7. 3. 2. 8. 5. 6. 4.
417 <title>Multilevel sorting</title>
419 <emphasis role="bold">With some decimal numbers</emphasis>:
420 Sorting first: by increasing integer parts,
421 second: by decreasing fractional parts.
423 <programlisting role="example"><![CDATA[
424 // Function getting the fractional parts
425 function r = get_frac(d)
431 2.1 0.1 1.3 1.2 0.1 1.2
432 0.3 1.2 2.3 0.3 1.2 2.1
433 0.1 1.2 1.1 1.2 2.2 1.1
434 2.3 1.3 0.1 2.3 0.1 0.1
435 0.1 2.2 2.1 0.2 1.1 0.3
438 [r, k] = %gsort_multilevel(d, "g", ["i" "d"], list(int, get_frac))
439 ]]> </programlisting>
442 0.3 0.1 0.1 1.2 1.1 2.2
443 0.3 0.1 1.3 1.2 1.1 2.2
444 0.3 0.1 1.3 1.2 2.3 2.1
445 0.2 0.1 1.2 1.2 2.3 2.1
446 0.1 0.1 1.2 1.1 2.3 2.1
449 2. 5. 29. 16. 25. 10.
450 17. 6. 9. 18. 28. 23.
451 30. 14. 11. 22. 4. 1.
452 20. 21. 7. 26. 12. 15.
453 3. 24. 8. 13. 19. 27.
457 <emphasis role="bold">With complex numbers</emphasis>:
458 Sorting, first: by increasing real parts, second: by increasing imaginary parts.
460 <programlisting role="example"><![CDATA[
461 //c = [-1 1 ; -1 0; 0 2; 0 %nan; 0 -1; 0 %inf ; 0 1; 1 %nan ; 1 1; 1 -1 ; -1 %nan ; 1 -%inf]
462 //c = matrix(squeeze(grand(1,"prm",complex(c(:,1), c(:,2)))), [3,4])
463 s = "complex([0,0,-1,-1;0,-1,1,1;1,1,0,0]," + ..
464 "[%inf,2,%nan,1;-1,0,-1,%nan;1,-%inf,1,%nan])";
466 [r, k] = %gsort_multilevel(c, "g", ["i" "i"], list(real, imag))
467 ]]> </programlisting>
471 0. + Infi 0. + 2.i -1. + Nani -1. + i
472 0. - i -1. + 0.i 1. - i 1. + Nani
473 1. + i 1. - Infi 0. + i 0. + Nani
476 -1. + 0.i 0. - i 0. + Infi 1. - i
477 -1. + i 0. + i 0. + Nani 1. + i
478 -1. + Nani 0. + 2.i 1. - Infi 1. + Nani
487 <emphasis role="bold">With some texts:</emphasis>
488 Sorting rows in columns, first by increasing lengths, second by alphabetical order
490 <programlisting role="example"><![CDATA[
492 "cc" "ca" "ab" "bbca" "b" "ccbc" "aab" "bca"
493 "ac" "bba" "aba" "bb" "a" "cac" "b" "b"
494 "aaaa" "ac" "b" "bbca" "bb" "bc" "aa" "ca"
495 "c" "ba" "cbb" "a" "aab" "abbb" "ac" "c"
496 "cbb" "b" "cabb" "bccc" "aba" "acb" "acb" "b"
497 "cba" "cc" "a" "abbb" "ab" "cc" "bba" "caaa"
500 [r, k] = %gsort_multilevel(t, "r", ["i" "i"], list(length, :))
501 ]]> </programlisting>
503 --> [r, k] = %gsort_multilevel(t, "r", ["i" "i"], list(length, :))
505 "c" "b" "a" "a" "a" "bc" "b" "b"
506 "ac" "ac" "b" "bb" "b" "cc" "aa" "b"
507 "cc" "ba" "ab" "abbb" "ab" "acb" "ac" "c"
508 "cba" "ca" "aba" "bbca" "bb" "cac" "aab" "ca"
509 "cbb" "cc" "cbb" "bbca" "aab" "abbb" "acb" "bca"
510 "aaaa" "bba" "cabb" "bccc" "aba" "ccbc" "bba" "caaa"
513 4. 5. 6. 4. 2. 3. 2. 2.
514 2. 3. 3. 2. 1. 6. 3. 5.
515 1. 4. 1. 6. 6. 5. 4. 4.
516 6. 1. 2. 1. 3. 2. 1. 3.
517 5. 6. 4. 3. 4. 4. 5. 1.
518 3. 2. 5. 5. 5. 1. 6. 6.
520 <!-- Display up to 6.0.2 (without extra blank lines)
523 !ac ac b bb b cc aa b !
524 !cc ba ab abbb ab acb ac c !
525 !cba ca aba bbca bb cac aab ca !
526 !cbb cc cbb bbca aab abbb acb bca !
527 !aaaa bba cabb bccc aba ccbc bba caaa !
531 <emphasis role="bold">With some polynomials:</emphasis>
532 Sorting first: by decreasing values of x^0, second: by increasing degrees.
534 <programlisting role="example"><![CDATA[
535 function c = get_coef(p, d)
536 // d : degree of the coeffs to return
537 c = matrix(coeff(p(:))(:,d+1), size(p))
540 P = ["[-x,1-2*x,2+2*x,1-x,2,-1-x;"
541 "1-x,-1+x,-1,x,1+2*x,2*x;"
542 "-2+x,1,-2,2+x,-x,-1-x]"];
547 [r, k] = %gsort_multilevel(P, "g", ["d" "i"], list(list(get_coef, 0), degree))
548 ]]> </programlisting>
552 -x 1 -2x 2 +2x 1 -x 2 -1 -x
553 1 -x -1 +x -1 x 1 +2x 2x
554 -2 +x 1 -2 2 +x -x -1 -x
556 --> [r, k] = %gsort_multilevel(P, "g", ["d" "i"], list(list(get_coef, 0), degree))
559 2 +2x 1 -x 1 +2x -x -1 +x -2
560 2 +x 1 -2x -x 2x -1 -x -2 +x
563 13. 6. 10. 11. 8. 18.
569 <refsection role="see also">
570 <title>See also</title>
571 <simplelist type="inline">
573 <link linkend="comparison">comparison</link>
576 <link linkend="strcmp">strcmp</link>
579 <link linkend="find">find</link>
582 <link linkend="overloading">overloading</link>
587 <title>Bibliography</title>
588 <para>Quick sort algorithm from Bentley & McIlroy's "Engineering a
589 Sort Function". Software---Practice and Experience,
594 <title>History</title>
597 <revnumber>5.4.0</revnumber>
599 gsort() can now be overloaded for unmanaged types.
603 <revnumber>6.1.0</revnumber>
607 Booleans can now be sorted.
610 Multilevel sorting added with the rankFuncs option.