gsort
сортирует массивы логических, числовых и строковых значений
Синтаксис
B = gsort(A) B = gsort(A, method) B = gsort(A, method, direction) B = gsort(A, method, directions, rankFuncs) [B, k] = 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 |
|
6.1.1 |
|
Report an issue | ||
<< find | Поиск и сортировка | members >> |