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'	:	General sorting: All elements of `A` are sorted (default method).
'r'	:	Rows of each column of `A` are sorted.
'c'	:	Columns of each row of `A` are sorted.
'lr'	:	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.
'lc'	:	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"	:	`k` is a matrix of size(A): `k(i)` is the linear index of `B(i)` in `A`, such that `B(:) = A(k)`.
"r"	:	`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)`.
"c"	:	`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,:)`.
"lr"	:	`k` is a column of size(A,1), such that `B = A(k,:)`.
"lc"	:	`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):

Sorting a matrix C of complex numbers, first: by increasing modulus, second: by increasing phase:
gsort(C, "g", ["i" "i"], list(abs, atan))
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, :))
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.
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.

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	Поиск и сортировка	members >>

Syntax

Arguments

Description

Sorting methods

Multilevel sorting

Examples

Multilevel sorting

See also

Bibliography

History