gsort

Аргументы

A

Скаляр, вектор, матрица или гиперматрица логических значений, целых, вещественных или комплексных чисел, или строковых значений. Разрежённые матрицы вещественных чисел, комплексных чисел или логических значений также могут быть отсортированы.

Разрешена перегрузка необрабатываемых типов.

method

Ключевое слово или индекс больше 0: метод сортировки:

'g'	:	Общая сортировка: сортируются все элементы в `A` (метод по умолчанию).
'r' или 1	:	Сортируются строки в каждом столбце в `A`.
'c' или 2	:	Сортируются столбцы в каждой строке в `A`.
'lr'	:	лексикографическая сортировка строк в `A`: Сортируются строки в соответствии со значениями в первом столбце. Если группа сортированных строк имеет то же значение, что и в столбце №1, то группа пересортировывается в соответствии со значениями в столбце №2, и так далее. Не применимо к гиперматрицам.
'lc'	:	лексикографическая сортировка столбцов в `A` (не для гиперматриц).

direction

направление сортировки: "d": в порядке уменьшения (по умолчанию); "i": в порядке увеличения.

directions

вектор символов "i" и "d", у которого столько же элементов, сколько элементов имеет rankFuncs. directions(k) используется для rankFuncs(k).

rankFuncs

список list(), элементы которого имеют следующие типы:

идентификатор fun функции на языке Scilab, либо встроенной функции.
: двоеточие. Ставится для такой fun, для которой fun(A) возвращает A.
список list(fun, param1, param2,..), в котором
- fun - это идентификатор функции Scilab или встроенной функции.
- param1, param2,.. - это параметры.
так что будет вызываться fun(A, param1, param2, ..).

Функции fun должны удовлетворять следующим условиям:

должны поддерживаться R=fun(A) или R=fun(A, param1, param2,..).
fun должна работать поэлементно, то есть: size(R)==size(A) и R(k) по сути равно A(k)
R должен быть простым сортируемым типом: логические значения, целые числа, вещественные значения, строковое значение.

Если A содержит комплексные числа, то можно определить обычные функции real, imag, abs, atan. Тогда atan(imag(A),real(A)) будет вызываться вместо atan(A).

B

Сортированный массив того же типа, кодирования и размера, что и A.

k

Массив десятичных целых чисел размера size(A): исходные индексы элементов B в A. Если A матрица, то в соответствии с выбранным методом

"g"	:	`k` это матрица размером `size(A)`: `k(i)` - это линейный индекс элемента `B(i)` в `A` такой, что `B(:) = A(k)`.
"r"	:	`k` это матрица размером `size(A)`: `k(i,j)` равна `1 ≤ index ≤ size(A,1)` элемента `B(i,j)` в столбце `A(:,j)`.
"c"	:	`k` это матрица размером `size(A)`: `k(i,j)` равна `1 ≤ index ≤ size(A,2)` элемента `B(i,j)` в строке `A(i,:)`.
"lr"	:	`k` - это столбец размером `size(A,1)` такой, что `B = A(k,:)`.
"lc"	:	`k` - это строка размером `size(A,2)` такая, что `B = A(:,k)`.

Описание

Функция gsort выполняет "быструю сортировку" различных типов данных. По умолчанию сортировка выполняется в порядке убывания.

Значения %nan считаются больше, чем %inf.

Комплексные числа по умолчанию сортируются только в соответствии с их модулями. Полная сортировка может быть достигнута, используя многоуровневый режим, через аргументы rankFuncs и directions. Например:

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

отсортирует массив C, сначала в порядке возрастания вещественных частей, и элементов у которых вещественные части равны, а затем в порядке убывания мнимых частей. Многоуровневый режим детально описан в соответствующем подразделе ниже.

Тексты сортируются в алфавитном порядке, с учётом регистра. Поддерживаются расширенные UTF-символы. The empty text "" is considered "smaller" than any other text.

Сортировка массивов логических значений главным образом полезна с помощью методов "r", "c", "lr" или "lc".

Какой бы метод ни выбрали, алгоритм сохраняет относительный порядок элементов с равными значениями.

Методы сортировки

B = gsort(A,'g', ..) сортирует все элементы в A и сохраняет сортированные элементы в первом столбце сверху вниз, а затем во втором столбце и т.д.

B = gsort(A,'c', ..) сортирует каждую строку в A. Каждый сортированный элемент находится в той же строке, что и в A, но возможно в другом столбце в соответствии с его рангом сортировки в строке.

B = gsort(A,'r', ..) сортирует каждый столбец в A. Каждый сортированный элемент находится в том же столбце, что и в A, но возможно в другой строке в соответствии с его рангом сортировки в строке.

B = gsort(A,'lr', ..) сортирует строки в A целиком в лексическом порядке. Две строки сравниваются и сортируются следующим образом. Сравниваются элементы их первых столбцов. Если их ранги не равны, то обе строки сортируются соответствующим образом. В противном случае сравниваются элементы их вторых столбцов, и т.д. вплоть до последнего столбца, если это потребуется.

B = gsort(A,'lc', ..) сортируются столбцы в A целиком, в лексикографическом порядке (см. выше).

Многоуровневая сортировка

Как отмечено выше, когда два сравниваемых элемента имеют одинаковые ранги, их исходный относительный порядок в A сохраняется в результирующей B.

Однако, во многих случаях, выходящих за рамки, может быть полезна и затребована многоуровневая сортировка: после выполнения первой сортировки в соответствии с первым критерием и направлением сортировки, можно указать второй критерий и направление сортировки и применить их к одинаковым элементам 1-го ранга, собранным после первой сортировки.

Если после двух первых сортировок некоторые элементы по-прежнему имеют одинаковый ранг, то можно определить и использовать третий уровень сортировки и т.д.

Применимые примеры (смотрите также раздел Примеры):

Сортировка матрицы C комплексных чисел, сначала в порядке увеличения модуля, затем в порядке увеличения фазы:
gsort(C, "g", ["i" "i"], list(abs, atan))
Сортировка столбцов матрицы T строковых значений, сначала в порядке увеличения длины, затем в обратном алфавитном порядке:
gsort(T, "c", ["i" "d"], list(length, :))
Сортировка матрицы P полиномов, сначала в порядке увеличения степени, затем в порядке уменьшения значения постоянного коэффициента 0-й степени:
```
function c = get_coef(p, i)
    // i: степень возвращаемого коэффициента
    c = matrix(coeff(p(:))(:,i+1), size(p))
endfunction

gsort(P, "c", ["i" "d"], list(degree, list(get_coef,0)))
```
В этом примере функция второго ранжирования позволяет определить степень i того коэффициента, который рассматривается в качестве значения вторичной сортировки.
Сортировка матрицы D десятичных чисел, сначала в порядке возрастания целых частей, затем в порядке уменьшения дробных частей:
```
function r = get_frac(numbers)
    r = numbers - int(numbers)
endfunction

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

Примеры

Сортировка элементов в строках:

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.

Лексикографическая сортировка строк:

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.

Лексикографическая сортировка логических столбцов:

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 ]==1;
m
[s, k] = gsort(m, "lc")  // сортировка столбцов в порядке убывания

--> m
 m  =
  F T F T T T F T
  F F T T T T F F
  F F T T F F F F

--> [s, k] = gsort(m, "lc")
 s  =
  T T T T T F F F
  T T T F F T F F
  T F F F F T F F

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

Многоуровневая сортировка

С некоторыми десятичными числами: Сначала сортировка в порядке возрастания целых частей, а затем в порядке убывания дробных частей.

// Функция получения дробных частей
function r=get_frac(d)
    r = d - int(d)
endfunction

// Несортированные данные
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
  ];
// Сортировка
[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.

С комплексными числами: Сортировка сначала в порядке увеличения вещественных частей, затем в порядке увеличения мнимых частей.

//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.

С некоторыми строковыми значениями: Сортировка строк в столбцах, сначала в порядке увеличения длины, затем в алфавитном порядке.

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.

С некоторыми полиномами: Сортировка сначала в порядке уменьшения значений x^0, затем в порядке увеличения степеней.

function c=get_coef(p, d)
    // d : степени возвращаемых коэффициентов
    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.

С гиперматрицей

Сортировка столбцов в каждой строке:

h = matrix([9,7,9,0,2,9,4,2,0,9,5,8,5,2,0,0], [2,4,2])
[s, k] = gsort(h, "c", "i")

--> h = matrix([9,7,9,0,2,9,4,2,0,9,5,8,5,2,0,0], [2,4,2])
 h  =
(:,:,1)
   9.   9.   2.   4.
   7.   0.   9.   2.
(:,:,2)
   0.   5.   5.   0.
   9.   8.   2.   0.

--> [s, k] = gsort(h, "c", "i")
 s  =
(:,:,1)
   2.   4.   9.   9.
   0.   2.   7.   9.
(:,:,2)
   0.   0.   5.   5.
   0.   2.   8.   9.

 k  =
(:,:,1)
   3.   4.   1.   2.
   2.   4.   1.   3.
(:,:,2)
   1.   4.   2.   3.
   4.   3.   2.   1.

Сортировка значений по страницам:

h = matrix([9,7,9,0,2,9,4,2,0,9,5,8,5,2,0,0], [2,4,2])
[s, k] = gsort(h, 3, "i")   // по третьей размерности = 'толщина' гиперматрицы

--> h = matrix([9,7,9,0,2,9,4,2,0,9,5,8,5,2,0,0], [2,4,2])
 h  =
(:,:,1)
   9.   9.   2.   4.
   7.   0.   9.   2.
(:,:,2)
   0.   5.   5.   0.
   9.   8.   2.   0.

--> [s, k] = gsort(h, 3, "i")
 s  =
(:,:,1)
   0.   5.   2.   0.
   7.   0.   2.   0.
(:,:,2)
   9.   9.   5.   4.
   9.   8.   9.   2.

 k  =
(:,:,1)
   2.   2.   1.   2.
   1.   1.   2.   2.
(:,:,2)
   1.   1.   2.   1.
   2.   2.   1.   1.

Смотрите также

сравнение — операторы сравнения, отношения
strcmp — сравнение символьных строк
find — даёт индексы элементов с ненулевым значением или значением %T
перегрузка — возможности перегрузки отображения, функций и операторов

Литература

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

История

Версия	Описание
5.4.0	Теперь gsort() может быть перегружена для неуправляемых типов.
6.1.0	Теперь можно сортировать логические значения. Многоуровневая сортировка, добавленная с помощью опции rankFuncs.
6.1.1	Для разрежённого входа, gsort() ранее была ограничена вещественными или комплексными векторами и только методом 'g'. Теперь она полностью способна к работе с разрежёнными векторами и двумерными матрицами логических, вещественных или комплексных чисел, всеми методами 'g, r, c, lr, lc'. Многоуровневая сортировка возможна для всех типов разрежённых входных данных. Теперь возможна сортировка вдоль размерности более 2.

Report an issue
<< find	Поиск и сортировка	members >>

Синтаксис

Аргументы

Описание

Методы сортировки

Многоуровневая сортировка

Примеры

Многоуровневая сортировка

С гиперматрицей

Смотрите также

Литература

История