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' : 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 forrankFuncs(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 thatfun(A)
returnsA
.  a
list(fun, param1, param2,..)
wherefun
is the identifier of a Scilab or builtin function.param1, param2,..
are parameters.
fun(A, param1, param2, ..)
will be called.
The functions
fun
must fullfill the following conditions:R=fun(A)
orR=fun(A, param1, param2,..)
must be supported.fun
must work in an elementwise way, meaning:size(R)==size(A)
, andR(k)
is about onlyA(k)
R
must be of simple sortable type: boolean, integer, real, text.
WhenA
are complex numbers, the usual functionsreal, imag, abs, atan
can be specified. Then,atan(imag(A),real(A))
will be called instead ofatan(A)
.  identifier
 B
 The sorted array, with
A
's data type, encoding, and sizes.  k
 Array of decimal integers, of size
size(A)
: Initial indices ofB
elements, inA
. IfA
is a matrix, according to the chosen method,"g" : k
is a matrix of size(A):k(i)
is the linear index ofB(i)
inA
, such thatB(:) = A(k)
."r" : k
is a matrix of size(A):k(i,j)
is the1 ≤ index ≤ size(A,1)
ofB(i,j)
in the columnA(:,j)
."c" : k
is a matrix of size(A):k(i,j)
is the1 ≤ index ≤ size(A,2)
ofB(i,j)
in the rowA(i,:)
."lr" : k
is a column of size(A,1), such thatB = A(k,:)
."lc" : k
is a row of size(A,2), such thatB = 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))
Texts are sorted in alphabetical order, in a casesensitive 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 multilevel 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 1strankequal 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 antialphabetical 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
0degree coefficient:
In this example, the second ranking function allows to specify the degree i of the coefficient to be considered as secondary sorting value.
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)))
 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,12*x,2+2*x,1x,2,1x;" "1x,1+x,1,x,1+2*x,2*x;" "2+x,1,2,2+x,x,1x]"]; 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 — find indices of boolean vector or matrix true elements
 overloading — возможности перегрузки отображения, функций и операторов
Bibliography
Quick sort algorithm from Bentley & McIlroy's "Engineering a Sort Function". SoftwarePractice and Experience, 23(11):12491265
History
Version  Description 
5.4.0  gsort() can now be overloaded for unmanaged types. 
6.1.0 

Comments
Add a comment:
Please login to comment this page.