Символы и строки

Быстрая сортировка

Эффективность алгоритма УлПир

Реализация алгоритма УлПир

Алгоритм УлПир

Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:

поменять местами очередной "рабочий" элемент с первым;
просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).

Часть программы, реализующую нулевой шаг алгоритма УлПир, мы привели в пункте "Просеивание", поэтому здесь ограничимся только реализацией основного шага 1:

for i:= N downto 2 do begin x:= a[1]; a[1]:= a[i]; a[i]:= x; j:= 1; while j<=((i-1)div 2) do begin k:= 2*j; if (k+1<=i-1) and (a[k]<a[k+1]) then k:= k+1; if a[k]>a[j] then begin x:= a[j]; a[j]:= a[k]; a[k]:= x; j:= k end else break endend;

Пример. Продолжим сортировку массива, для которого мы уже построили пирамиду: [12,11,8,7,10,6,5,4,2,9,3,1]. С целью экономии места мы не будем далее прорисовывать структуру пирамиды, оставляя это несложное упражнение читателям. Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а полужирный шрифт - элементы, исключенные из дальнейшей обработки:

1) Меняем местами a[1] и a[12]: [1,11,8,7,10,6,5,4,2,9,3,12];2) Просеиваем элемент a[1], получаем: [11,10,8,7,9,6,5,4,2,1,3,12];3) Меняем местами a[1] и a[11]: [3,10,8,7,9,6,5,4,2,1,11,12];4) Просеиваем a[1], получаем: [10,9,8,7,3,6,5,4,2,1,11,12];5) Меняем местами a[1] и a[10]: [1,9,8,7,3,6,5,4,2,10,11,12];6) Просеиваем элемент a[1]: [9,7,8,4,3,6,5,1,2,10,11,12];7) Меняем местами a[1] и a[9]: [2,7,8,4,3,6,5,1,9,10,11,12];8) Просеиваем элемент a[1]: [8,7,6,4,3,2,5,1,9,10,11,12];9) Меняем местами a[1] и a[8]: [1,7,6,4,3,2,5,8,9,10,11,12];10) Просеиваем элемент a[1]: [7,4,6,1,3,2,5,8,9,10,11,12];11) Меняем местами a[1] и a[7]: [5,4,6,1,3,2,7,8,9,10,11,12];12) Просеиваем элемент a[1]: [6,4,5,1,3,2,7,8,9,10,11,12];13) Меняем местами a[1] и a[6]: [2,4,5,1,3,6,7,8,9,10,11,12];14) Просеиваем элемент a[1]: [5,4,2,1,3,6,7,8,9,10,11,12];15) Меняем местами a[1] и a[5]: [3,4,2,1,5,6,7,8,9,10,11,12];16) Просеиваем элемент a[1]: [4,3,2,1,5,6,7,8,9,10,11,12];17) Меняем местами a[1] и a[4]: [1,3,2,4,5,6,7,8,9,10,11,12];18) Просеиваем элемент a[1]: [3,1,2,4,5,6,7,8,9,10,11,12];19) Меняем местами a[1] и a[3]: [2,1,3,4,5,6,7,8,9,10,11,12];20) Просеивать уже ничего не нужно;21) Меняем местами a[1] и a[2]: [1,2,3,4,5,6,7,8,9,10,11,12];22) Просеивать ничего не нужно, сортировка закончена.

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.

В среднем этот алгоритм имеет сложность, пропорциональную N*log N.

Существует еще один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка⁴⁾. Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернемся к ее изучению после того, как познакомимся с рекурсивными процедурами и функциями (см. лекцию 9).

5. Лекция: Символы и строки. Множества

Две предыдущие лекции были посвящены произвольным массивам. Перейдем теперь к изучению массивов специального вида - линейных массивов, состоящих только из символов, - строк. Кроме того, сами символы мы тоже не обойдем вниманием.