Иллюстрированный самоучитель по задачам и примерам Assembler

Улучшение классических методов сортировки

Приведенные выше четыре метода сортировки – базовые. Их обычно рассматривают как основу для последующего обсуждения и совершенствования. Ниже мы рассмотрим несколько усовершенствованных методов сортировки, после чего вы сможете оценить эффективность их всех.

Сортировка Шелла

Приводимый ниже алгоритм сортировки (программа 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+1, в результате получается последовательность смещений: 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.1): // массив смещений размерностью 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=<n?
ja @@ml:конец итерации при очередном mas_dist[]
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:
Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.