Приведенные выше четыре метода сортировки — базовые. Их обычно рассматривают как основу для последующего обсуждения и совершенствования. Ниже мы рассмотрим несколько усовершенствованных методов сортировки, после чего вы сможете оценить эффективность их всех.
Сортировка Шелла
Приводимый ниже алгоритм сортировки (программа prg4_107.asm) носит имя автора, который предложил его в 1959 году. Суть его состоит в том, что сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии h. На каждом шаге значение h изменяется, пока не станет (обязательно) равно 1. Важно правильно подобрать значения h для каждого шага. От этого зависит скорость работы алгоритма. В качестве значений h могут быть следующие числовые последовательности: (4, 2, 1), (8, 4, 2, 1) и даже (7, 5, 3, 1). Последовательности чисел можно вычислять аналитически. Так, Кнут предлагает следующие соотношения:
- Nk-1 = 3Nk+1, в результате получается последовательность смещений: 1, 4, 13,40,121...
- Nk-1, = 2Nk+l, в результате получается последовательность смещений: 1, 3, 7, 15, 31...
Подобное аналитическое получение последовательности смещений
дает возможность разрабатывать программу, которая динамически
подстраивается под конкретный сортируемый массив.
Отметим, что если h=1, то алгоритм сортировки Шелла вырождается в сортировку прямыми включениями.
Существует несколько вариантов алгоритма данной сортировки. Вариант,
рассмотренный ниже, основывается на алгоритме, предложенном Кнутом.
ПРОГРАММА prg4_107
//prg4_107 - программа на псевдоязыке сортировки Шелла
//Вход: mas_dist=(7,5,3.1) - массив смещений: mas[n] - неупорядоченная
последовательность байтовых двоичных значений. //Выход: mas[n] -упорядоченная последовательность байтовых двоичных значений.
-ПЕРЕМЕННЫЕ
INT_BYTE t=4; //количество элементов в массиве смещений
INT_BYTE mas[n]; //сортируемый массив размерностью п (О..п-1)
INT_BYTE mas_dist[t]=(7.5,3,l): // массив смещений размерностью t (O..t-1)
INT_BYTE h=0 //очередное смещение из mas_dist[]
INT_BYTE X: i=0: j-0; s=0 // i. j. s - индексы
НАЧ_ПРОГ
ДЛЯ s:=0 ДО t-1 НАЧ_БЛОК_1
h:=mas_dist[s] ДЛЯ j:4i ДО n-1 НАЧ_БЛ0К_2
i:=j-h: X:=mas[i]
@@d4: ЕСЛИ Х>= mas[i] TO ПЕРЕЙТИ_НА №66 mas[i+h]:=mas[i]: i:=i-h
ЕСЛИ 1>0 ТО ЛЕРЕЙТИ__НА @@d4 Ш6: mas[i+h]:=x К0Н_БЛ0К_2 КОН_БЛОК_1
КОН_ПРОГ
:prg4_107.asm - программа на ассемблере сортировки Шелла
.data
: задаем массив
masdb 44,55.12.42.94.18,06,67
n=$-mas
X db 0
:задаем массив расстояний
mas_dist db 7.5.3.1
t=$-mas_dist ;t - количество элементов в массиве расстояний
.code
xorbx.bx :в bx - очередное смещение из mas_dist[] :dl
movcx.t :цикл по t (внешний)
movsi.O :индекс по mas_dist[] (?@d2: push ex
mov bl,mas_dist[si] :в bx - очередное смещение из mas_dist[]
inc si push si :ДЛЯ j:=h ДО n-1
mov di.bx ' ;di - это j :j:=h+l - это неявно для нумерации массива с нуля @@d3: cmpdi.n-1 ;j=
mov si ,di
sub si.bx :i:=j-h: si - это i
mov al ,mas[di] ;x:=mas[j]
movx.al :x:=mas[j] @@d4: :ЕСЛИ Х>= mas[i] TO ПЕРЕЙТИ_НА №й6
mov al,x
cmpal ,mas[si]
jae@@d6
:d5 - mas[i+h]:=mas[i]: i:=i-h push di push si popdi
adddi.bx :i+h
mov al, mas[si] :mas[i+h]:=mas[i]
movmas[di],al :mas[i+h]:=mas[i] pop di
subsi.bx ;i:=i-h
cmpsi.O ;ЕСЛИ i>0 TO ПЕРЕЙТИ_НА @@d4
jg Ш4
@@d6: ;mas[i+h]:=x
push di push si pop di
adddi.bx ;i+h
mov al .x
movmas[di].al ;mas[i+h]:=x popdi
incdi :j:=j+l
jmp ШЗ @@ml: pop si pop ex
loop Ш2 @@exit:
Сортировка с помощью дерева
Следующий алгоритм (программа prgl0_229.asm) является улучшением сортировки прямым выбором. Автор алгоритма сортировки с помощью дерева — Дж. У. Дж. Уильяме (1964 год). В литературе этот алгоритм носит название «пирамидальной» сортировки. Если обсужденные выше сортировки интуитивно понятны, то алгоритм данной сортировки необходимо пояснить подробнее. Этот алгоритм предназначен для сортировки последовательности чисел, которые являются отображением в памяти дерева специальной структуры — пирамиды. Пирамида — помеченное корневое двоичное дерево заданной высоты h, обладающее тремя свойствами:
- каждая конечная вершина имеет высоту h или h-1;
- каждая конечная вершина высоты h нажщится слева от любой конечной вершины высоты h-1;
- метка любой вершины больше метки любой следующей за ней вершины.
На рис. 2.3 изображено несколько деревьев, из которых лишь одно Т4 является пирамидой.
Рис. 2.3. Примеры деревьев (Т4 — пирамида)
Такая структура пирамид позволяет компактно располагать их в
памяти. Например, пирамида, показанная на рисунке, в памяти будет
представлена следующим массивом: 27, 9, 14, 8, 5, 11, 7, 2, 3.
Оказывается, что такая последовательность чисел легко подвергается
сортировке.
Таким образом, сортировка массива в соответствии с алгоритмом
пирамидальной сортировки осуществляется в два этапа: на первом этапе
массив преобразуется в отображение пирамиды; на втором — осуществляется
собственно сортировка. Соответственно нами должны быть разработаны две
процедуры для выполнения задач каждого из этих двух этапов.
ПРОЦЕДУРА insert_item_in_tree (i. mas. N) //
//insert_item_in_tree - процедура на псевдоязыке вставки элемента на свое место
в пирамиду //Вход: mas[n] - сформированная не до конца пирамида: 1 - номер добавляемого элемента
в пирамиду из mas[n] (с конца): n - длина пирамиды //Выход:действие - элемент добавлен в пирамиду.
НАЧ_ПРОГ
j:=i @@ml: k:=2*j: h-k+1
ЕСЛИ (1=
КОН_ЕСЛИ @@m6: ЕСЛИ tnas[k]>mas[l] TO ПЕРЕЙТИ_НА @@т4
ИНАЧЕ ПЕРЕЙТИ_НА @@тЗ
КОН_ЕСЛИ @@т4: x:=mas[j]
mas[j]:=mas[k]
j:=k
mas[k]:=x ПЕРЕЙТИ_НА (a0ml (а@тЗ: x:=mas[j]
mas[j]:=mas[l]
mas[l]:=x
ПЕРЕЙТИ_НА @@ml*
@@m2: ЕСЛИ (k==n И mas[j]
КОН_ЕСЛИ @@m7: x:=mas[j]
mas[j]:=mas[n]
;m-n/2 - значение, равное половине числа элементов массива mas
push si push ex
movj.si :j\»1 @@m4:
movsi.j :i->si
movax.j :k:=2*j; l:-k+l
shlax.l :j*2
movk.ax : k :=j*2
inc ax
movl.ax :l:»k+l
cmpax.m :l
moval ,raas[si-l] ;ax:-mas[j]
mov di,k
emp al ,mas[di-l]
jna @@m6
inc di
emp al.mas[di-l]
jna @@m6
jmp @@m2
@@m6: ;условие выполнилось:
;2j+l+
mov al ,mas[di-1] ;ax:=mas[k]
inc di
emp al,mas[di-l] :mas[k]>mas[l]
jna ШтЗ
mov al ,raas[si-l]
movx.al ;x:=rnas[j]
dec di
mov al ,mas[di-l]
movmas[si-l].al :mas[j]:=mas[k]
movj.di :j:=k
mov al .x
movmas[di-l],al :mas[k]:=x
jmp @?m4
:@@m3: x:=mas[j] ;ПЕРЕЙТИ_НА @@ml №m3: :mas[k] =< mas[l]
mov al,mas[si-l]
movx.al :x:=mas[j]
mov al,mas[di-l]
movmas[si-l].al ;mas[j]:=mas[l]
movj.di :j:=l
mov al ,x
movmas[di-l].al ;mas[l]:=x
jmp @@m4 Шт2: ; условие не выполнилось: 2j+l+
emp ax.m
Нахождение медианы
Медиана - элемент последовательности, значение которго не больше значений одной половины этой последовательности. Например, медианой последовательности чисел 38 7 5 90 65 8 74 43 2 является 38.
оответствующая отсортированная последовательность будет выглядеть так: 2 5 7 8 38 43 65 74 90.
Задачу нахождения медианы можно решить просто — предварительно
отсортировать исходный массив и выбрать средний элемент. Но К. Хоор
предлагает метод, который решает задачу нахождения медианы быстрее и
соответственно может рассматриваться как вспомогательный для реализации
других задач. Достоинство метода К. Хоора заключается в том, что с его
помощью можно эффективно находить не только медиану, но и значение k-го
по величине элемента последовательности. Например, третьим по величине
элементом приведенной выше последовательности будет 7.
Значение k-го элемента массива определяется по формуле k=n/2, где п — длина исходной последовательности чисел.
Ниже приведена программа prg4_123.asm, которая находит элемент-медиану
массива. Аналогичную функцию выполняет и процедура median, но процедура
отличается тем, что ее можно вызывать динамически во время работы
программы, в которой она используется.
ПРОГРАММА prg4_123
//
//prg4_123 - программа на псевдоязыке нахождения k-го по величине элемента массива mas
длиною п. Для нахождения медианы к=п/2. //Вход: mas[n] - неупорядоченная последовательность двоичных значений: к - номер
искомого по величине элемента mas[n]. //Выход: х - значение к-го по величине элемента последовательности mas[n].
// .....
ПЕРЕМЕННЫЕ
INT_BYTE n: ;длина mas[n]
INT_BYTE mas[n]: //сортируемый массив размерностью n (О..n-l)
INTJYTE X:W;i=0: j=0; 1=0; г=0 // j: 1; г - индексы
НАЧПРОГ
1:=1: г:=п ПОКА 1<г ДЕЛАТЬ НАЧ_БЛОК_1 х:=а[к]: 1:=1: j:=r ПОВТОРИТЬ
ПОКА a[i]
.data
jge $+6
movR.di :R<-J :цикл(1)конец jmp @@m8
Быстрая сортировка
Последний рассматриваемый нами алгоритм (программа
prglO_223.asm) является улучшенным вариантом сортировки прямым обменом.
Этот метод разработан К. Хоором в 1962 году и назван им «быстрой
сортировкой». Эффективность быстрой сортировки зависит от степени
упорядоченности исходного массива. Для сильно неупорядоченных массивов —
это один из лучших методов сортировки. В худшем случае, когда исходный
массив почти упорядочен, его быстрая сортировка по эффективности не
намного лучше сортировки прямым обменом.
Идея метода быстрой сортировки состоит в следующем. Первоначально
среди элементов сортируемого массива mas[l. .n] выбирается один mas[k],
относительно которого выполняется переупорядочивание остальных элементов
по принципу — элементы mas[i]
ПРОГРАММА prg27_136
//prg27_136 (по Кнуту) - программа на псевдоязыке «быстрой сортировки»
массива. //Вход: mas[n] - неупорядоченная последовательность двоичных
значений длиной п. //Выход: mas[n] -упорядоченная последовательность
двоичных значений длиной n.
ПЕРЕМЕННЫЕ
INTJYTE n: //длина mas[n]
INT_BYTE mas[n]; //сортируемый массив размерностью п (О..п-1)
INTJYTE К; TEMP: i=0; j=0: 1=0: г=0; // i. j. 1. г - индексы
INT_WORD M=l //длина подпоследовательности, для которой производится сортировка методом
прямых включений //для отладки возьмем М=1 НАЧ_ПРОГ
ЕСЛИ M
ВКЛЮЧИТЬ_В_СТЕК (Offffh) //Offffh - признак пустого стека q2: i :-l: j:-r+l: k:=mas[l] q3: ЕСЛИ i=
ЕСЛИ mas[i]
ЕСЛИ K
Iq2: ;1:-1: j:-r+l: k:-nas[l] movsi.L ;i(si):=L mov di . R incdi ;j(di):=R+l xor ax.ax mov al ,mas[si] mov k.al
q3: :ЕСЛИ 1-sj-l TO ПЕРЕЙТИ_НА qq3 inc si ;i:=i+l cmp si.di :i=
q4: decdi ;j:=j-l cmpdi.si :j>=i-l jb q5 mov al ,k :ЕСЛИ K
»jb q4 q5: ;ЕСЛИ j>i TO ПЕРЕЙТИ_НА q6 cmpdi.si :j=
mas[j] xchg mas[di].dl xchg mas[si].dl jmpq3 ;ПЕРЕЙТИ_НА q3 q7: ;ЕСЛИ
r-j>j-l>M TO mov ax,г
subax.di ;r-j->ax mov bx.di
subbx.l :j-l->bx cmpax.bx :r-j>j-l ??? jl q7_m4
cmpbx.M ;j-l>M ??? jleq7_m3 ;1, r-j>j-l>M - в стек (j+l.r); r:=j-l; перейти на шаг q2
mov ax.di inc ax push ax
(push г mov r.di dec г :г:=j -1 q7_m4: ;r-j>M ??? cmp ax.M jg q7_m2 cmp bx. M
jleq8 ;4. j-l>M>r-j - r:=j-l: перейти на шаг q2
mov r.di
dec г
jmpq2 q7_m3: cmpax.M
jleq8 ;3. r-j>M>j-l - l:=j+l: перейти на шаг q2
mov 1,di
inc 1
jmpq2 q7_m2: :2. j-l>r-j>M - в стек (l.j-1); l:=j+l; перейти на шаг q2
push 1
mov ax.di
inc ax
push ax
mov 1 ,di
inc 1
jmpq2 q8: извлекаем из стека очередную пару (l.r)
pop г
cmpr.Offffh :ЕСЛИ r<>0ffffh TO ПЕРЕЙТИ_НА q2
je q9
pop!
jmpq2 q9: ;сортировка методом пряных включений - при М=1 этот шаг можно опустить (что и сделано
для экономии места)
Обратите внимание на каскад сравнений шага q7, целью которых является проверка выполнения следующих неравенств:
- r-j>=j-1>M — в стек (j+l,r); r:-j-1; перейти на шаг q2;
- j-1>r-j>M — в стек (1, j-1); I :=j+1; перейти на шаг q2;
- r-j>M>j-l — 1 :=j+1; перейти на шаг q2;
- j-1>M>r-j — г:=j-1; перейти на шаг q2.
Проверка этих неравенств реализуется в виде попарных сравнений, последовательность которых выглядит так, как показано на рис. 2.4.
Рис. 2.4. Последовательность сравнений шага q7
За подробностями алгоритма можно обратиться к тому 3 «Сортировка и поиск» книги Кнута .
Сушествует другой вариант алгоритма этой сортировки — у Вирта в книге «Алгоритмы + структуры данных - программы» [4]. Но у него используется понятие медианы последовательности. Задачу нахождения медианы мы рассматривали выше. Эта задача интересна еще и тем, что она, по сути, является одной из задач поиска, рассмотрению которых посвящен следующий раздел.