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  * Copyright (C) 2012 - 2016 - Scilab Enterprises
   6  * Copyright (C) 2018 - 2020 - Samuel GOUGEON
   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"
  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">
  20     <refnamediv>
  21         <refname>gsort</refname>
  22         <refpurpose>sorting by quick sort algorithm</refpurpose>
  23     </refnamediv>
  24     <refsynopsisdiv>
  25         <title>Syntax</title>
  26         <synopsis>
  27             B = gsort(A)
  28             B = gsort(A, method)
  29             B = gsort(A, method, direction)
  30             B = gsort(A, method, directions, rankFuncs)
  31             [B, k] = gsort(..)
  32         </synopsis>
  33     </refsynopsisdiv>
  34     <refsection>
  35         <title>Arguments</title>
  36         <variablelist>
  37             <varlistentry>
  38                 <term>A</term>
  39                 <listitem>
  40                     Scalar, vector, matrix or hypermatrix of booleans, integers, real or complex
  41                     numbers, or text, or a sparse vector of real numbers.
  42                     <note>
  43                         Overloading for unhandled types is allowed.
  44                     </note>
  45                     <para/>
  46                 </listitem>
  47             </varlistentry>
  48             <varlistentry>
  49                 <term>method</term>
  50                 <listitem>
  51                     A keyword: The sorting method:
  52                     <informaltable>
  53                         <tr valign="top">
  54                             <th>'g'</th><td>:</td>
  55                             <td>General sorting: All elements of <literal>A</literal> are sorted
  56                                 (default method).
  57                             </td>
  58                         </tr>
  59                         <tr valign="top">
  60                             <th>'r'</th><td>:</td>
  61                             <td>Rows of each column of <literal>A</literal> are sorted.</td>
  62                         </tr>
  63                         <tr valign="top">
  64                             <th>'c'</th><td>:</td>
  65                             <td>Columns of each row of <literal>A</literal> are sorted.</td>
  66                         </tr>
  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.
  73                             </td>
  74                         </tr>
  75                         <tr valign="top"><th>'lc'</th><td>:</td>
  76                             <td>lexicographic sort of the columns of <literal>A</literal>
  77                                 (not for hypermatrices).
  78                             </td>
  79                         </tr>
  80                     </informaltable>
  81                     <para/>
  82                 </listitem>
  83             </varlistentry>
  84             <varlistentry>
  85                 <term>direction</term>
  86                 <listitem>
  87                     "d" for <emphasis role="bold">d</emphasis>ecreasing order (default), or
  88                     "i" for <emphasis role="bold">i</emphasis>ncreasing one.
  89                     <para/>
  90                 </listitem>
  91             </varlistentry>
  92             <varlistentry>
  93                 <term>directions</term>
  94                 <listitem>
  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>.
  98                     <para/>
  99                 </listitem>
 100             </varlistentry>
 101             <varlistentry>
 102                 <term>rankFuncs</term>
 103                 <listitem>
 104                     list() whose elements are among the following type:
 105                     <itemizedlist>
 106                         <listitem>
 107                             identifier <literal>fun</literal> of a function in Scilab language
 108                             or of a builtin function.
 109                         </listitem>
 110                         <listitem>
 111                             : colon. It stands for a <literal>fun</literal> such that
 112                             <literal>fun(A)</literal> returns <literal>A</literal>.
 113                         </listitem>
 114                         <listitem>
 115                             a <literal>list(fun, param1, param2,..)</literal> where
 116                             <itemizedlist>
 117                                 <listitem>
 118                                     <literal>fun</literal> is the identifier of a Scilab or
 119                                     builtin function.
 120                                 </listitem>
 121                                 <listitem>
 122                                     <literal>param1, param2,..</literal> are parameters.
 123                                 </listitem>
 124                             </itemizedlist>
 125                             such that <literal>fun(A, param1, param2, ..)</literal> will be called.
 126                         </listitem>
 127                     </itemizedlist>
 128                     <para>
 129                         The functions <literal>fun</literal> must fullfill the following conditions:
 130                         <itemizedlist>
 131                             <listitem>
 132                                 <literal>R=fun(A)</literal> or <literal>R=fun(A, param1, param2,..)</literal>
 133                                 must be supported.
 134                             </listitem>
 135                             <listitem>
 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>
 139                             </listitem>
 140                             <listitem>
 141                                 <literal>R</literal> must be of simple sortable type: boolean,
 142                                 integer, real, text.
 143                             </listitem>
 144                         </itemizedlist>
 145                     </para>
 146                     <para>
 147                         <note>
 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>.
 152                         </note>
 153                     </para>
 154                 </listitem>
 155             </varlistentry>
 156             <varlistentry>
 157                 <term>B</term>
 158                 <listitem>
 159                     The sorted array, with  <literal>A</literal>'s data type, encoding, and sizes.
 160                     <para/>
 161                 </listitem>
 162             </varlistentry>
 163             <varlistentry>
 164                 <term>k</term>
 165                 <listitem>
 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,
 169                     <table>
 170                     <tr>
 171                         <th valign="top">"g"</th><td>:</td>
 172                         <td>
 173                             <literal>k</literal> is a matrix of size(A): <literal>k(i)</literal>
 174                             is the linear index
 175                             of <literal>B(i)</literal> in <literal>A</literal>, such that
 176                             <literal>B(:) = A(k)</literal>.
 177                         </td>
 178                     </tr>
 179                     <tr>
 180                         <th valign="top">"r"</th><td>:</td>
 181                         <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>.
 185                         </td>
 186                     </tr>
 187                     <tr>
 188                         <th valign="top">"c"</th><td>:</td>
 189                         <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>.
 193                         </td>
 194                     </tr>
 195                     <tr>
 196                         <th valign="top">"lr"</th><td>:</td>
 197                         <td>
 198                             <literal>k</literal> is a column of size(A,1), such that
 199                             <literal>B = A(k,:)</literal>.
 200                         </td>
 201                     </tr>
 202                     <tr>
 203                         <th valign="top">"lc"</th><td>:</td>
 204                         <td>
 205                             <literal>k</literal> is a row of size(A,2), such that
 206                             <literal>B = A(:,k)</literal>.
 207                         </td>
 208                     </tr>
 209                     </table>
 210                     <para/>
 211                 </listitem>
 212             </varlistentry>
 213         </variablelist>
 214     </refsection>
 215     <refsection>
 216         <title>Description</title>
 217         <para>
 218             <literal>gsort</literal> performs a "quick sort" for various native data types.
 219             By default, sorting is performed in decreasing order.
 220         </para>
 221         <para>
 222             <literal>%nan</literal> values are considered greater than <literal>%inf</literal>.
 223         </para>
 224         <para>
 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.
 228             Example:
 229         </para>
 230         <para>
 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.
 235         </para>
 236         <para>
 237             Texts are sorted in alphabetical order, in a case-sensitive way.
 238             Extended UTF characters are supported.
 239         </para>
 240         <para>
 241             <note>
 242                 Whatever is the chosen method, <emphasis role="bold">the algorithm preserves the
 243                 relative order of elements with equal values.
 244             </emphasis>
 245             </note>
 246         </para>
 247         <refsect3>
 248             <title>Sorting methods</title>
 249             <para>
 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.
 253             </para>
 254             <para>
 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.
 258             </para>
 259             <para>
 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.
 263             </para>
 264             <para>
 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.
 270             </para>
 271             <para>
 272                 <emphasis role="bold">B = gsort(A,'lc', ..)</emphasis> sorts columns of A,
 273                 as a whole, in a lexical way (see above).
 274             </para>
 275         </refsect3>
 276         <refsect3>
 277             <title>Multilevel sorting</title>
 278             <para>
 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> .
 281             </para>
 282             <para>
 283                 However, in many cases, going beyond through a multi-level sorting can be useful
 284                 and required:
 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.
 288             </para>
 289             <para>
 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.
 292             </para>
 293             <para>
 294                 <emphasis role="bold">Applied examples</emphasis> (see also the Examples section):
 295                 <orderedlist>
 296                     <listitem>
 297                         <emphasis>Sorting a matrix C of complex numbers,
 298                         first: by increasing modulus, second: by increasing phase</emphasis>:
 299                         <para/>
 300                         <literal>gsort(C, "g", ["i" "i"], list(abs, atan))</literal>
 301                         <para/>
 302                     </listitem>
 303                     <listitem>
 304                         <emphasis>Sorting the columns of a matrix T of texts,
 305                         first: by increasing length, second: in anti-alphabetical order</emphasis>:
 306                         <para/>
 307                         <literal>gsort(T, "c", ["i" "d"], list(length, :))</literal>
 308                         <para/>
 309                     </listitem>
 310                     <listitem>
 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>:
 314                         <screen>
 315 function c = get_coef(p, i)
 316     // i: degree of the coeff to return
 317     c = matrix(coeff(p(:))(:,i+1), size(p))
 318 endfunction
 319
 320 gsort(P, "c", ["i" "d"], list(degree, list(get_coef,0)))
 321 </screen>
 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.
 324                         <para/>
 325                     </listitem>
 326                     <listitem>
 327                         <emphasis>Sorting a matrix D of decimal numbers,
 328                         first: by increasing integer parts, second: by decreasing fractional parts</emphasis>:
 329                         <screen>
 330 function r = get_frac(numbers)
 331     r = numbers - int(numbers)
 332 endfunction
 333
 334 gsort(D, "g", ["i" "d"], list(int, get_frac))
 335 </screen>
 336                     </listitem>
 337                     <para/>
 338                 </orderedlist>
 339             </para>
 340         </refsect3>
 341     </refsection>
 342     <refsection>
 343         <title>Examples</title>
 344         <para>
 345             Sorting elements in rows:
 346         </para>
 347         <programlisting role="example"><![CDATA[
 348 m = [ 0.  2.  1.  2.  1.  0.
 349       1.  1.  3.  1.  0.  3.
 350       2.  3   3.  2.  1.  1. ];
 351
 352 [s, k] = gsort(m, "c")
 353 ]]>     </programlisting>
 354         <screen><![CDATA[
 355 --> [s, k] = gsort(m, "c")
 356  s  =
 357    2.   2.   1.   1.   0.   0.
 358    3.   3.   1.   1.   1.   0.
 359    3.   3.   2.   2.   1.   1.
 360
 361  k  =
 362    2.   4.   3.   5.   1.   6.
 363    3.   6.   1.   2.   4.   5.
 364    2.   3.   1.   4.   5.   6.
 365 ]]></screen>
 366         <para/>
 367         <para>
 368             Lexicographic sorting of rows:
 369         </para>
 370         <programlisting role="example"><![CDATA[
 371 v = ['Scilab' '3.1'
 372      'xcos'   '4.0'
 373      'xcos'   '3.1'
 374      'Scilab' '2.7'
 375      'xcos'   '2.7'
 376      'Scilab' '4.0'];
 377
 378 [s, k] = gsort(v,'lr','i'); s, k'
 379 ]]>     </programlisting>
 380             <screen><![CDATA[
 381 --> [s, k] = gsort(v,'lr','i'); s, k'
 382  s  =
 383   "Scilab"  "2.7"
 384   "Scilab"  "3.1"
 385   "Scilab"  "4.0"
 386   "xcos"    "2.7"
 387   "xcos"    "3.1"
 388   "xcos"    "4.0"
 389
 390  ans  =
 391    4.   1.   6.   5.   3.   2.
 392 ]]></screen>
 393         <para/>
 394         <para/>
 395         <para>
 396             Lexicographic sorting of columns:
 397         </para>
 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.
 402      ];
 403
 404 [s, k] = gsort(m, "lc", "i")  // sorting columns
 405 ]]>     </programlisting>
 406             <screen><![CDATA[
 407 --> [s, k] = gsort(m, "lc", "i")
 408  s  =
 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.
 412
 413  k  =
 414    1.   7.   3.   2.   8.   5.   6.   4.
 415 ]]></screen>
 416     <refsect3>
 417         <title>Multilevel sorting</title>
 418         <para>
 419             <emphasis role="bold">With some decimal numbers</emphasis>:
 420             Sorting first: by increasing integer parts,
 421             second: by decreasing fractional parts.
 422         </para>
 423         <programlisting role="example"><![CDATA[
 424 // Function getting the fractional parts
 425 function r = get_frac(d)
 426     r = d - int(d)
 427 endfunction
 428
 429 // Unsorted data
 430 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
 436   ];
 437 // Sorting
 438 [r, k] = %gsort_multilevel(d, "g", ["i" "d"], list(int, get_frac))
 439 ]]>     </programlisting>
 440         <screen><![CDATA[
 441  r  =
 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
 447
 448  k  =
 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.
 454 ]]></screen>
 455         <para/>
 456         <para>
 457             <emphasis role="bold">With complex numbers</emphasis>:
 458             Sorting, first: by increasing real parts, second: by increasing imaginary parts.
 459         </para>
 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])";
 465 c = evstr(s)
 466 [r, k] = %gsort_multilevel(c, "g", ["i" "i"], list(real, imag))
 467 ]]>     </programlisting>
 468     <screen><![CDATA[
 469 --> c = evstr(s)
 470  c  =
 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
 474
 475  r  =
 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
 479
 480  k  =
 481    5.    2.   1.    8.
 482    10.   9.   12.   3.
 483    7.    4.   6.    11.
 484 ]]></screen>
 485         <para/>
 486         <para>
 487             <emphasis role="bold">With some texts:</emphasis>
 488             Sorting rows in columns, first by increasing lengths, second by alphabetical order
 489         </para>
 490         <programlisting role="example"><![CDATA[
 491 t = [
 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"
 498   ];
 499
 500 [r, k] = %gsort_multilevel(t, "r", ["i" "i"], list(length, :))
 501 ]]>     </programlisting>
 502         <screen><![CDATA[
 503 --> [r, k] = %gsort_multilevel(t, "r", ["i" "i"], list(length, :))
 504  r  =
 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"
 511
 512  k  =
 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.
 519 ]]></screen>
 520 <!--  Display up to 6.0.2 (without extra blank lines)
 521  r  =
 522 !c     b    a     a     a    bc    b    b     !
 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  !
 528 -->
 529         <para/>
 530         <para>
 531             <emphasis role="bold">With some polynomials:</emphasis>
 532             Sorting first: by decreasing values of x^0, second: by increasing degrees.
 533         </para>
 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))
 538 endfunction
 539
 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]"];
 543
 544 x = varn(%s,"x");
 545 P = evstr(P)
 546
 547 [r, k] = %gsort_multilevel(P, "g", ["d" "i"], list(list(get_coef, 0), degree))
 548 ]]>     </programlisting>
 549         <screen><![CDATA[
 550 --> P = evstr(P)
 551  P  =
 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
 555
 556 --> [r, k] = %gsort_multilevel(P, "g", ["d" "i"], list(list(get_coef, 0), degree))
 557  r  =
 558   2      1      1 -x   x   -1     -1 -x
 559   2 +2x  1 -x   1 +2x  -x  -1 +x  -2
 560   2 +x   1 -2x  -x     2x  -1 -x  -2 +x
 561
 562  k  =
 563    13.   6.   10.   11.   8.    18.
 564    7.    2.   14.   15.   5.    9.
 565    12.   4.   1.    17.   16.   3.
 566 ]]></screen>
 567     </refsect3>
 568     </refsection>
 569     <refsection role="see also">
 570         <title>See also</title>
 571         <simplelist type="inline">
 572             <member>
 573                 <link linkend="comparison">comparison</link>
 574             </member>
 575             <member>
 576                 <link linkend="strcmp">strcmp</link>
 577             </member>
 578             <member>
 579                 <link linkend="find">find</link>
 580             </member>
 581             <member>
 582                 <link linkend="overloading">overloading</link>
 583             </member>
 584         </simplelist>
 585     </refsection>
 586     <refsection>
 587         <title>Bibliography</title>
 588         <para>Quick sort algorithm from Bentley &amp; McIlroy's "Engineering a
 589             Sort Function". Software---Practice and Experience,
 590             23(11):1249-1265
 591         </para>
 592     </refsection>
 593     <refsection>
 594         <title>History</title>
 595         <revhistory>
 596             <revision>
 597                 <revnumber>5.4.0</revnumber>
 598                 <revremark>
 599                     gsort() can now be overloaded for unmanaged types.
 600                 </revremark>
 601             </revision>
 602             <revision>
 603                 <revnumber>6.1.0</revnumber>
 604                 <revremark>
 605                     <itemizedlist>
 606                         <listitem>
 607                             Booleans can now be sorted.
 608                         </listitem>
 609                         <listitem>
 610                             Multilevel sorting added with the rankFuncs option.
 611                         </listitem>
 612                     </itemizedlist>
 613                 </revremark>
 614             </revision>
 615         </revhistory>
 616     </refsection>
 617 </refentry>