Scilab 6.1.0
Change language to:
English - Français - Português - Русский

Please note that the recommended version of Scilab is 2023.1.0. This page might be outdated.
See the recommended documentation of this function

# gsort

sorting by quick sort algorithm

### Syntax

```B = gsort(A)
B = gsort(A, method)
B = gsort(A, method, direction)
B = gsort(A, method, directions, rankFuncs)
[B, k] = gsort(..)```

### Arguments

A
Scalar, vector, matrix or hypermatrix of booleans, integers, real or complex numbers, or text, or a sparse vector of real numbers.
 Overloading for unhandled types is allowed.

method
A keyword: The sorting method:
'g' 'r' : General sorting: All elements of `A` are sorted (default method). : Rows of each column of `A` are sorted. : Columns of each row of `A` are sorted. : lexicographic sort of the rows of `A`: Sorts rows according to values in the first column. If a group of sorted rows have the same value in column #1, resorts the group according to values in column #2. etc. Not applicable to hypermatrices. : lexicographic sort of the columns of `A` (not for hypermatrices).

direction
"d" for decreasing order (default), or "i" for increasing one.

directions
vector of "i" and "d" characters, with as many elements than `rankFuncs` has. `directions(k)` is used for `rankFuncs(k)`.

rankFuncs
list() whose elements are among the following type:
• identifier `fun` of a function in Scilab language or of a builtin function.
• : colon. It stands for a `fun` such that `fun(A)` returns `A`.
• a `list(fun, param1, param2,..)` where
• `fun` is the identifier of a Scilab or builtin function.
• `param1, param2,..` are parameters.
such that `fun(A, param1, param2, ..)` will be called.

The functions `fun` must fullfill the following conditions:

• `R=fun(A)` or `R=fun(A, param1, param2,..)` must be supported.
• `fun` must work in an element-wise way, meaning: `size(R)==size(A)`, and `R(k)` is about only `A(k)`
• `R` must be of simple sortable type: boolean, integer, real, text.

 When `A` are complex numbers, the usual functions `real, imag, abs, atan` can be specified. Then, `atan(imag(A),real(A))` will be called instead of `atan(A)`.

B
The sorted array, with `A`'s data type, encoding, and sizes.

k
Array of decimal integers, of size `size(A)`: Initial indices of `B` elements, in `A`. If `A` is a matrix, according to the chosen method,
"g" "r" : `k` is a matrix of size(A): `k(i)` is the linear index of `B(i)` in `A`, such that `B(:) = A(k)`. : `k` is a matrix of size(A): `k(i,j)` is the `1 ≤ index ≤ size(A,1)` of `B(i,j)` in the column `A(:,j)`. : `k` is a matrix of size(A): `k(i,j)` is the `1 ≤ index ≤ size(A,2)` of `B(i,j)` in the row `A(i,:)`. : `k` is a column of size(A,1), such that `B = A(k,:)`. : `k` is a row of size(A,2), such that `B = A(:,k)`.

### Description

`gsort` performs a "quick sort" for various native data types. By default, sorting is performed in decreasing order.

`%nan` values are considered greater than `%inf`.

Complex numbers are by default sorted only according to their moduli. Complete sorting can be achieved using the multilevel mode, through the `rankFuncs` and `directions` arguments. Example:

`M = gsort(C, "g", ["i" "d"], list(real, imag))`

will sort the array C, first by increasing real parts, and for elements of equal real parts, second by decreasing imaginary parts. The multilevel mode is described with details in a dedicated subsection below.

Texts are sorted in alphabetical order, in a case-sensitive way. Extended UTF characters are supported.

 Whatever is the chosen method, the algorithm preserves the relative order of elements with equal values.

##### Sorting methods

B = gsort(A,'g', ..) sorts all elements of `A`, and stores sorted elements in the first column from top to bottom, then in the second column, etc.

B = gsort(A,'c', ..) sorts each row of A. Each sorted element is on the same row as in A, but possibly on another column corresponding to its sorting rank on the row.

B = gsort(A,'r', ..) sorts each column of A. Each sorted element is on the same column as in A, but possibly on another row corresponding to its sorting rank.

B = gsort(A,'lr', ..) sorts rows of A, as a whole, in a lexical way. Two rows are compared and sorted in the following way: The elements of their first column are compared. If their ranks are not equal, both rows are sorted accordingly. Otherwise, the elements of their second column are compared. etc... up to the last column if it is required.

B = gsort(A,'lc', ..) sorts columns of A, as a whole, in a lexical way (see above).

##### Multilevel sorting

As noted above, when two compared elements have equal ranks, their initial relative order in `A` is preserved in the result `B` .

However, in many cases, going beyond through a multi-level sorting can be useful and required: After the first sort performed according to a first criterion and sorting direction, it is possible to define a second criterion and sorting direction and apply them to 1st-rank-equal elements gathered by the first sort.

If after the two first sorting some elements have still the same ranks, it is possible to define and use a 3rd sorting level, etc.

Applied examples (see also the Examples section):

1. Sorting a matrix C of complex numbers, first: by increasing modulus, second: by increasing phase:

`gsort(C, "g", ["i" "i"], list(abs, atan))`

2. Sorting the columns of a matrix T of texts, first: by increasing length, second: in anti-alphabetical order:

`gsort(T, "c", ["i" "d"], list(length, :))`

3. Sorting a matrix P of polynomials, first: by increasing degree, second: by decreasing value of the constant 0-degree coefficient:
```function c = get_coef(p, i)
// i: degree of the coeff to return
c = matrix(coeff(p(:))(:,i+1), size(p))
endfunction

gsort(P, "c", ["i" "d"], list(degree, list(get_coef,0)))
```
In this example, the second ranking function allows to specify the degree i of the coefficient to be considered as secondary sorting value.

4. Sorting a matrix D of decimal numbers, first: by increasing integer parts, second: by decreasing fractional parts:
```function r = get_frac(numbers)
r = numbers - int(numbers)
endfunction

gsort(D, "g", ["i" "d"], list(int, get_frac))
```

### Examples

Sorting elements in rows:

```m = [ 0.  2.  1.  2.  1.  0.
1.  1.  3.  1.  0.  3.
2.  3   3.  2.  1.  1. ];

[s, k] = gsort(m, "c")```
```--> [s, k] = gsort(m, "c")
s  =
2.   2.   1.   1.   0.   0.
3.   3.   1.   1.   1.   0.
3.   3.   2.   2.   1.   1.

k  =
2.   4.   3.   5.   1.   6.
3.   6.   1.   2.   4.   5.
2.   3.   1.   4.   5.   6.
```

Lexicographic sorting of rows:

```v = ['Scilab' '3.1'
'xcos'   '4.0'
'xcos'   '3.1'
'Scilab' '2.7'
'xcos'   '2.7'
'Scilab' '4.0'];

[s, k] = gsort(v,'lr','i'); s, k'```
```--> [s, k] = gsort(v,'lr','i'); s, k'
s  =
"Scilab"  "2.7"
"Scilab"  "3.1"
"Scilab"  "4.0"
"xcos"    "2.7"
"xcos"    "3.1"
"xcos"    "4.0"

ans  =
4.   1.   6.   5.   3.   2.
```

Lexicographic sorting of columns:

```m  = [ 0.  1.  0.  1.  1.  1.  0.  1.
0.  0.  1.  1.  1.  1.  0.  0.
0.  0.  1.  1.  0.  0.  0.  0.
];

[s, k] = gsort(m, "lc", "i")  // sorting columns```
```--> [s, k] = gsort(m, "lc", "i")
s  =
0.   0.   0.   1.   1.   1.   1.   1.
0.   0.   1.   0.   0.   1.   1.   1.
0.   0.   1.   0.   0.   0.   0.   1.

k  =
1.   7.   3.   2.   8.   5.   6.   4.
```

##### Multilevel sorting

With some decimal numbers: Sorting first: by increasing integer parts, second: by decreasing fractional parts.

```// Function getting the fractional parts
function r=get_frac(d)
r = d - int(d)
endfunction

// Unsorted data
d = [
2.1   0.1   1.3   1.2   0.1   1.2
0.3   1.2   2.3   0.3   1.2   2.1
0.1   1.2   1.1   1.2   2.2   1.1
2.3   1.3   0.1   2.3   0.1   0.1
0.1   2.2   2.1   0.2   1.1   0.3
];
// Sorting
[r, k] = gsort(d, "g", ["i" "d"], list(int, get_frac))```
``` r  =
0.3   0.1   0.1   1.2   1.1   2.2
0.3   0.1   1.3   1.2   1.1   2.2
0.3   0.1   1.3   1.2   2.3   2.1
0.2   0.1   1.2   1.2   2.3   2.1
0.1   0.1   1.2   1.1   2.3   2.1

k  =
2.    5.    29.   16.   25.   10.
17.   6.    9.    18.   28.   23.
30.   14.   11.   22.   4.    1.
20.   21.   7.    26.   12.   15.
3.    24.   8.    13.   19.   27.
```

With complex numbers: Sorting, first: by increasing real parts, second: by increasing imaginary parts.

```//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]
//c = matrix(squeeze(grand(1,"prm",complex(c(:,1), c(:,2)))), [3,4])
s = "complex([0,0,-1,-1;0,-1,1,1;1,1,0,0]," + ..
"[%inf,2,%nan,1;-1,0,-1,%nan;1,-%inf,1,%nan])";
c = evstr(s)
[r, k] = gsort(c, "g", ["i" "i"], list(real, imag))```
```--> c = evstr(s)
c  =
0. + Infi   0. + 2.i   -1. + Nani  -1. + i
0. - i     -1. + 0.i    1. - i      1. + Nani
1. + i      1. - Infi   0. + i      0. + Nani

r  =
-1. + 0.i    0. - i     0. + Infi   1. - i
-1. + i      0. + i     0. + Nani   1. + i
-1. + Nani   0. + 2.i   1. - Infi   1. + Nani

k  =
5.    2.   1.    8.
10.   9.   12.   3.
7.    4.   6.    11.
```

With some texts: Sorting rows in columns, first by increasing lengths, second by alphabetical order

```t = [
"cc"    "ca"    "ab"    "bbca"  "b"     "ccbc"  "aab"   "bca"
"ac"    "bba"   "aba"   "bb"    "a"     "cac"   "b"     "b"
"aaaa"  "ac"    "b"     "bbca"  "bb"    "bc"    "aa"    "ca"
"c"     "ba"    "cbb"   "a"     "aab"   "abbb"  "ac"    "c"
"cbb"   "b"     "cabb"  "bccc"  "aba"   "acb"   "acb"   "b"
"cba"   "cc"    "a"     "abbb"  "ab"    "cc"    "bba"   "caaa"
];

[r, k] = gsort(t, "r", ["i" "i"], list(length, :))```
```--> [r, k] = gsort(t, "r", ["i" "i"], list(length, :))
r  =
"c"     "b"    "a"     "a"     "a"    "bc"    "b"    "b"
"ac"    "ac"   "b"     "bb"    "b"    "cc"    "aa"   "b"
"cc"    "ba"   "ab"    "abbb"  "ab"   "acb"   "ac"   "c"
"cba"   "ca"   "aba"   "bbca"  "bb"   "cac"   "aab"  "ca"
"cbb"   "cc"   "cbb"   "bbca"  "aab"  "abbb"  "acb"  "bca"
"aaaa"  "bba"  "cabb"  "bccc"  "aba"  "ccbc"  "bba"  "caaa"

k  =
4.   5.   6.   4.   2.   3.   2.   2.
2.   3.   3.   2.   1.   6.   3.   5.
1.   4.   1.   6.   6.   5.   4.   4.
6.   1.   2.   1.   3.   2.   1.   3.
5.   6.   4.   3.   4.   4.   5.   1.
3.   2.   5.   5.   5.   1.   6.   6.
```

With some polynomials: Sorting first: by decreasing values of x^0, second: by increasing degrees.

```function c=get_coef(p, d)
// d : degree of the coeffs to return
c = matrix(coeff(p(:))(:,d+1), size(p))
endfunction

P = ["[-x,1-2*x,2+2*x,1-x,2,-1-x;"
"1-x,-1+x,-1,x,1+2*x,2*x;"
"-2+x,1,-2,2+x,-x,-1-x]"];

x = varn(%s,"x");
P = evstr(P)

[r, k] = gsort(P, "g", ["d" "i"], list(list(get_coef, 0), degree))```
```--> P = evstr(P)
P  =
-x      1 -2x   2 +2x   1 -x   2      -1 -x
1 -x  -1 +x   -1       x      1 +2x   2x
-2 +x   1      -2       2 +x   -x     -1 -x

--> [r, k] = gsort(P, "g", ["d" "i"], list(list(get_coef, 0), degree))
r  =
2      1      1 -x   x   -1     -1 -x
2 +2x  1 -x   1 +2x  -x  -1 +x  -2
2 +x   1 -2x  -x     2x  -1 -x  -2 +x

k  =
13.   6.   10.   11.   8.    18.
7.    2.   14.   15.   5.    9.
12.   4.   1.    17.   16.   3.
```

### See also

• comparison — 比較, 関係演算子
• strcmp — 文字列を比較
• find — 論理値ベクトルまたは行列のtrue要素の添え字を見つける
• overloading — 表示,関数および演算子オーバーロード機能

### Bibliography

Quick sort algorithm from Bentley & McIlroy's "Engineering a Sort Function". Software---Practice and Experience, 23(11):1249-1265

### History

 Version Description 5.4.0 gsort() can now be overloaded for unmanaged types. 6.1.0 Booleans can now be sorted. Multilevel sorting added with the rankFuncs option.
 Report an issue << find searchandsort members >>

 Copyright (c) 2022-2023 (Dassault Systèmes)Copyright (c) 2017-2022 (ESI Group)Copyright (c) 2011-2017 (Scilab Enterprises)Copyright (c) 1989-2012 (INRIA)Copyright (c) 1989-2007 (ENPC)with contributors Last updated:Tue Feb 25 08:53:19 CET 2020