1 <?xml version="1.0" encoding="UTF-8"?>
3 * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
4 * Copyright (C) 2008 - INRIA
5 * Copyright (C) 2012 - 2016 - Scilab Enterprises
6 * Copyright (C) 2018 - 2020 - Samuel GOUGEON
7 * Copyright (C) 2020 - Stanislav KROTER
9 * This file is hereby licensed under the terms of the GNU GPL v2.0,
10 * pursuant to article 5.3.4 of the CeCILL v.2.1.
11 * This file was originally licensed under the terms of the CeCILL v2.1,
12 * and continues to be available under such terms.
13 * For more information, see the COPYING file which you should have received
14 * along with this program.
17 <refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink"
18 xmlns:svg="http://www.w3.org/2000/svg" xmlns:ns5="http://www.w3.org/1999/xhtml"
19 xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook"
20 xmlns:scilab="http://www.scilab.org" xml:id="gsort" xml:lang="ru">
22 <refname>gsort</refname>
23 <refpurpose>сортировка по алгоритму быстрой сортировки</refpurpose>
26 <title>Синтаксис</title>
30 B = gsort(A, method, direction)
31 B = gsort(A, method, directions, rankFuncs)
36 <title>Аргументы</title>
41 Скаляр, вектор, матрица или гиперматрица логических значений, целых,
42 вещественных или комплексных чисел, или текстов. Sparse matrices of
43 real numbers, of complex numbers, or of booleans can also be sorted.
45 Разрешена перегрузка необрабатываемых типов.
53 Ключевое слово: метод сортировки:
56 <th>'g'</th><td>:</td>
57 <td>Общая сортировка: сортируются все элементы в <literal>A</literal>
58 ( метод по умолчанию).
62 <th>'r'</th><td>:</td>
63 <td>Сортируются строки в каждом столбце в <literal>A</literal>.</td>
66 <th>'c'</th><td>:</td>
67 <td>Сортируются столбцы в каждой строке в <literal>A</literal>.</td>
69 <tr valign="top"><th>'lr'</th><td>:</td>
71 лексикографическая сортировка строк в <literal>A</literal>:
72 Сортируются строки в соответствии со значениями в первом столбце.
73 Если группа сортированных строк имеет то же значение, что и в
74 столбце №1, то группа пересортировывается в соответствии со
75 значениями в столбце №2, и так далее. Не применимо к гиперматрицам.
78 <tr valign="top"><th>'lc'</th><td>:</td>
80 лексикографическая сортировка столбцов в <literal>A</literal>
89 <term>direction</term>
91 направление сортировки:
92 "d": в порядке уменьшения (по умолчанию);
93 "i": в порядке увеличения.
98 <term>directions</term>
100 вектор символов "i" и "d", у которого столько же элементов, сколько
101 элементов имеет <varname>rankFuncs</varname>.
102 <literal>directions(k)</literal> используется для
103 <varname>rankFuncs(k)</varname>.
108 <term>rankFuncs</term>
110 список <literal>list()</literal>, элементы которого имеют следующие типы:
113 идентификатор <literal>fun</literal> функции на языке Scilab,
114 либо встроенной функции.
117 : двоеточие. Ставится для такой <literal>fun</literal>, для которой
118 <literal>fun(A)</literal> возвращает <literal>A</literal>.
121 список <literal>list(fun, param1, param2,..)</literal>, в котором
124 <literal>fun</literal> - это идентификатор функции Scilab или
128 <literal>param1, param2,..</literal> - это параметры.
131 так что будет вызываться <literal>fun(A, param1, param2, ..)</literal>.
135 Функции <literal>fun</literal> должны удовлетворять следующим условиям:
138 должны поддерживаться <literal>R=fun(A)</literal> или
139 <literal>R=fun(A, param1, param2,..)</literal>.
142 <literal>fun</literal> должна работать поэлементно, то есть:
143 <literal>size(R)==size(A)</literal> и <literal>R(k)</literal>
144 по сути равно <literal>A(k)</literal>
147 <literal>R</literal> должен быть простым сортируемым типом:
148 логические значения, целые числа, вещественные значения, текст.
154 Если <literal>A</literal> содержит комплексные числа, то можно
155 определить обычные функции <literal>real, imag, abs, atan</literal>.
156 Тогда <literal>atan(imag(A),real(A))</literal> будет вызываться
157 вместо <literal>atan(A)</literal>.
165 Сортированный массив того же типа, кодирования и размера, что и <literal>A</literal>.
172 Массив десятичных целых чисел размера <literal>size(A)</literal>:
173 исходные индексы элементов <literal>B</literal> в <literal>A</literal>.
174 Если <literal>A</literal> матрица, то в соответствии с выбранным методом
177 <th valign="top">"g"</th><td>:</td>
179 <literal>k</literal> это матрица размером <literal>size(A)</literal>:
180 <literal>k(i)</literal> - это линейный индекс элемента
181 <literal>B(i)</literal> в <literal>A</literal> такой, что <literal>B(:) = A(k)</literal>.
185 <th valign="top">"r"</th><td>:</td>
187 <literal>k</literal> это матрица размером <literal>size(A)</literal>:
188 <literal>k(i,j)</literal> равна <literal>1 ≤ index ≤ size(A,1)</literal>
189 элемента <literal>B(i,j)</literal> в столбце <literal>A(:,j)</literal>.
193 <th valign="top">"c"</th><td>:</td>
195 <literal>k</literal> это матрица размером <literal>size(A)</literal>:
196 <literal>k(i,j)</literal> равна <literal>1 ≤ index ≤ size(A,2)</literal>
197 элемента <literal>B(i,j)</literal> в строке <literal>A(i,:)</literal>.
201 <th valign="top">"lr"</th><td>:</td>
203 <literal>k</literal> - это столбец размером <literal>size(A,1)</literal>
204 такой, что <literal>B = A(k,:)</literal>.
208 <th valign="top">"lc"</th><td>:</td>
210 <literal>k</literal> - это строка размером <literal>size(A,2)</literal>
211 такая, что <literal>B = A(:,k)</literal>.
221 <title>Описание</title>
223 Функция <literal>gsort</literal> выполняет "быструю сортировку" различных типов
224 данных. По умолчанию сортировка выполняется в порядке убывания.
227 Значения <literal>%nan</literal> считаются больше, чем <literal>%inf</literal>.
230 Комплексные числа по умолчанию сортируются только в соответствии с их модулями.
231 Полная сортировка может быть достигнута, используя многоуровневый режим, через
232 аргументы <varname>rankFuncs</varname> и <varname>directions</varname>.
236 <literal>M = gsort(C, "g", ["i" "d"], list(real, imag))</literal><para/>
237 отсортирует массив <literal>C</literal>, сначала в порядке возрастания вещественных
238 частей, и элементов у которых вещественные части равны, а затем в порядке убывания
239 мнимых частей. Многоуровневый режим детально описан в соответствующем подразделе ниже.
242 Тексты сортируются в алфавитном порядке, с учётом регистра.
243 Поддерживаются расширенные UTF-символы.
246 Сортировка массивов логических значений главным образом полезна с помощью методов
247 "r", "c", "lr" или "lc".
251 Какой бы метод ни выбрали, <emphasis role="bold">алгоритм сохраняет относительный порядок элементов с равными значениями</emphasis>.
255 <title>Методы сортировки</title>
257 <emphasis role="bold">B = gsort(A,'g', ..)</emphasis> сортирует все элементы в
258 <varname>A</varname> и сохраняет сортированные элементы в первом столбце сверху
259 вниз, а затем во втором столбце и т.д.
262 <emphasis role="bold">B = gsort(A,'c', ..)</emphasis> сортирует каждую строку в
263 <varname>A</varname>. Каждый сортированный элемент находится в той же строке, что
264 и в <varname>A</varname>, но возможно в другом столбце в соответствии с его
265 рангом сортировки в строке.
268 <emphasis role="bold">B = gsort(A,'r', ..)</emphasis> сортирует каждый столбец в
269 <varname>A</varname>. Каждый сортированный элемент находится в том же столбце,
270 что и в <varname>A</varname>, но возможно в другой строке в соответствии с его
271 рангом сортировки в строке.
274 <emphasis role="bold">B = gsort(A,'lr', ..)</emphasis> сортирует строки в
275 <varname>A</varname> целиком в лексическом порядке. Две строки сравниваются и
276 сортируются следующим образом. Сравниваются элементы их первых столбцов. Если их
277 ранги не равны, то обе строки сортируются соответствующим образом. В противном
278 случае сравниваются элементы их вторых столбцов, и т.д. вплоть до последнего
279 столбца, если это потребуется.
282 <emphasis role="bold">B = gsort(A,'lc', ..)</emphasis> сортируются столбцы в
283 <varname>A</varname> целиком, в лексикографическом порядке (см. выше).
287 <title>Многоуровневая сортировка</title>
289 Как отмечено выше, когда два сравниваемых элемента имеют одинаковые ранги, их
290 исходный относительный порядок в <varname>A</varname> сохраняется в
291 результирующей <varname>B</varname>.
294 Однако, во многих случаях, выходящих за рамки, может быть полезна и затребована
295 многоуровневая сортировка:
296 после выполнения первой сортировки в соответствии с первым критерием и
297 направлением сортировки, можно указать второй критерий и направление сортировки и
298 применить их к одинаковым элементам 1-го ранга, собранным после первой
302 Если после двух первых сортировок некоторые элементы по-прежнему имеют одинаковый
303 ранг, то можно определить и использовать третий уровень сортировки и т.д.
306 <emphasis role="bold">Применимые примеры</emphasis> (смотрите также раздел
310 <emphasis>Сортировка матрицы <literal>C</literal> комплексных чисел,
311 сначала в порядке увеличения модуля, затем в порядке увеличения
314 <literal>gsort(C, "g", ["i" "i"], list(abs, atan))</literal>
318 <emphasis>Сортировка столбцов матрицы <literal>T</literal> текстов,
319 сначала в порядке увеличения длины, затем в обратном алфавитном
322 <literal>gsort(T, "c", ["i" "d"], list(length, :))</literal>
326 <emphasis>Сортировка матрицы <literal>P</literal> полиномов,
327 сначала в порядке увеличения степени, затем в порядке уменьшения значения постоянного коэффициента 0-й степени</emphasis>:
329 function c = get_coef(p, i)
330 // i: степень возвращаемого коэффициента
331 c = matrix(coeff(p(:))(:,i+1), size(p))
334 gsort(P, "c", ["i" "d"], list(degree, list(get_coef,0)))
336 В этом примере функция второго ранжирования позволяет определить степень
337 <literal>i</literal> того коэффициента, который рассматривается в
338 качестве значения вторичной сортировки.
342 <emphasis>Сортировка матрицы <literal>D</literal> десятичных чисел,
343 сначала в порядке возрастания целых частей, затем в порядке уменьшения дробных частей</emphasis>:
345 function r = get_frac(numbers)
346 r = numbers - int(numbers)
349 gsort(D, "g", ["i" "d"], list(int, get_frac))
358 <title>Примеры</title>
360 Сортировка элементов в строках:
363 <programlisting role="example"><![CDATA[
364 m = [ 0. 2. 1. 2. 1. 0.
368 [s, k] = gsort(m, "c")
369 ]]> </programlisting>
371 --> [s, k] = gsort(m, "c")
384 Лексикографическая сортировка строк:
387 <programlisting role="example"><![CDATA[
395 [s, k] = gsort(v,'lr','i'); s, k'
396 ]]> </programlisting>
398 --> [s, k] = gsort(v,'lr','i'); s, k'
412 Лексикографическая сортировка логических столбцов:
415 <programlisting role="example"><![CDATA[
416 m = [ 0 1 0 1 1 1 0 1
418 0 0 1 1 0 0 0 0 ]==1;
420 [s, k] = gsort(m, "lc") // сортировка столбцов в порядке убывания
421 ]]> </programlisting>
429 --> [s, k] = gsort(m, "lc")
436 4. 5. 6. 2. 8. 3. 1. 7.
440 <title>Многоуровневая сортировка</title>
442 <emphasis role="bold">С некоторыми десятичными числами</emphasis>:
443 Сначала сортировка в порядке возрастания целых частей, а затем в порядке убывания
447 <programlisting role="example"><![CDATA[
448 // Функция получения дробных частей
449 function r = get_frac(d)
453 // Несортированные данные
455 2.1 0.1 1.3 1.2 0.1 1.2
456 0.3 1.2 2.3 0.3 1.2 2.1
457 0.1 1.2 1.1 1.2 2.2 1.1
458 2.3 1.3 0.1 2.3 0.1 0.1
459 0.1 2.2 2.1 0.2 1.1 0.3
462 [r, k] = gsort(d, "g", ["i" "d"], list(int, get_frac))
463 ]]> </programlisting>
466 0.3 0.1 0.1 1.2 1.1 2.2
467 0.3 0.1 1.3 1.2 1.1 2.2
468 0.3 0.1 1.3 1.2 2.3 2.1
469 0.2 0.1 1.2 1.2 2.3 2.1
470 0.1 0.1 1.2 1.1 2.3 2.1
473 2. 5. 29. 16. 25. 10.
474 17. 6. 9. 18. 28. 23.
475 30. 14. 11. 22. 4. 1.
476 20. 21. 7. 26. 12. 15.
477 3. 24. 8. 13. 19. 27.
481 <emphasis role="bold">С комплексными числами</emphasis>:
482 Сортировка сначала в порядке увеличения вещественных частей, затем в порядке
483 увеличения мнимых частей.
486 <programlisting role="example"><![CDATA[
487 //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]
488 //c = matrix(squeeze(grand(1,"prm",complex(c(:,1), c(:,2)))), [3,4])
489 s = "complex([0,0,-1,-1;0,-1,1,1;1,1,0,0]," + ..
490 "[%inf,2,%nan,1;-1,0,-1,%nan;1,-%inf,1,%nan])";
492 [r, k] = gsort(c, "g", ["i" "i"], list(real, imag))
493 ]]> </programlisting>
497 0. + Infi 0. + 2.i -1. + Nani -1. + i
498 0. - i -1. + 0.i 1. - i 1. + Nani
499 1. + i 1. - Infi 0. + i 0. + Nani
502 -1. + 0.i 0. - i 0. + Infi 1. - i
503 -1. + i 0. + i 0. + Nani 1. + i
504 -1. + Nani 0. + 2.i 1. - Infi 1. + Nani
513 <emphasis role="bold">С некоторыми текстами:</emphasis>
514 Сортировка строк в столбцах, сначала в порядке увеличения длины, затем в алфавитном
518 <programlisting role="example"><![CDATA[
520 "cc" "ca" "ab" "bbca" "b" "ccbc" "aab" "bca"
521 "ac" "bba" "aba" "bb" "a" "cac" "b" "b"
522 "aaaa" "ac" "b" "bbca" "bb" "bc" "aa" "ca"
523 "c" "ba" "cbb" "a" "aab" "abbb" "ac" "c"
524 "cbb" "b" "cabb" "bccc" "aba" "acb" "acb" "b"
525 "cba" "cc" "a" "abbb" "ab" "cc" "bba" "caaa"
528 [r, k] = gsort(t, "r", ["i" "i"], list(length, :))
529 ]]> </programlisting>
531 --> [r, k] = gsort(t, "r", ["i" "i"], list(length, :))
533 "c" "b" "a" "a" "a" "bc" "b" "b"
534 "ac" "ac" "b" "bb" "b" "cc" "aa" "b"
535 "cc" "ba" "ab" "abbb" "ab" "acb" "ac" "c"
536 "cba" "ca" "aba" "bbca" "bb" "cac" "aab" "ca"
537 "cbb" "cc" "cbb" "bbca" "aab" "abbb" "acb" "bca"
538 "aaaa" "bba" "cabb" "bccc" "aba" "ccbc" "bba" "caaa"
541 4. 5. 6. 4. 2. 3. 2. 2.
542 2. 3. 3. 2. 1. 6. 3. 5.
543 1. 4. 1. 6. 6. 5. 4. 4.
544 6. 1. 2. 1. 3. 2. 1. 3.
545 5. 6. 4. 3. 4. 4. 5. 1.
546 3. 2. 5. 5. 5. 1. 6. 6.
549 <!-- Display up to 6.0.2 (without extra blank lines)
552 !ac ac b bb b cc aa b !
553 !cc ba ab abbb ab acb ac c !
554 !cba ca aba bbca bb cac aab ca !
555 !cbb cc cbb bbca aab abbb acb bca !
556 !aaaa bba cabb bccc aba ccbc bba caaa !
559 <emphasis role="bold">С некоторыми полиномами:</emphasis>
560 Сортировка сначала в порядке уменьшения значений x^0, затем в порядке увеличения
564 <programlisting role="example"><![CDATA[
565 function c = get_coef(p, d)
566 // d : степени возвращаемых коэффициентов
567 c = matrix(coeff(p(:))(:,d+1), size(p))
570 P = ["[-x,1-2*x,2+2*x,1-x,2,-1-x;"
571 "1-x,-1+x,-1,x,1+2*x,2*x;"
572 "-2+x,1,-2,2+x,-x,-1-x]"];
577 [r, k] = gsort(P, "g", ["d" "i"], list(list(get_coef, 0), degree))
578 ]]> </programlisting>
582 -x 1 -2x 2 +2x 1 -x 2 -1 -x
583 1 -x -1 +x -1 x 1 +2x 2x
584 -2 +x 1 -2 2 +x -x -1 -x
586 --> [r, k] = gsort(P, "g", ["d" "i"], list(list(get_coef, 0), degree))
589 2 +2x 1 -x 1 +2x -x -1 +x -2
590 2 +x 1 -2x -x 2x -1 -x -2 +x
593 13. 6. 10. 11. 8. 18.
600 <refsection role="see also">
601 <title>Смотрите также</title>
602 <simplelist type="inline">
604 <link linkend="comparison">сравнение</link>
607 <link linkend="strcmp">strcmp</link>
610 <link linkend="find">find</link>
613 <link linkend="overloading">перегрузка</link>
618 <title>Литература</title>
619 <para>Quick sort algorithm from Bentley & McIlroy's "Engineering a
620 Sort Function". Software---Practice and Experience,
625 <title>История</title>
628 <revnumber>5.4.0</revnumber>
630 Теперь gsort() может быть перегружена для неуправляемых типов.
634 <revnumber>6.1.0</revnumber>
638 Теперь можно сортировать логические значения.
641 Многоуровневая сортировка, добавленная с помощью опции rankFuncs.
647 <revnumber>6.1.1</revnumber>
649 gsort() ранее была ограничена вещественными или комплексными
650 векторами и только методом 'g'. Теперь она полностью способна
651 к работе с разрежёнными векторами и двумерными матрицами логических,
652 вещественных или комплексных чисел, всеми методами 'g, r, c, lr, lc'.
653 Многоуровневая сортировка возможна для всех типов разрежённых входных данных.