Улучшение классических методов сортировки
Приведенные выше четыре метода сортировки – базовые. Их обычно рассматривают как основу для последующего обсуждения и совершенствования. Ниже мы рассмотрим несколько усовершенствованных методов сортировки, после чего вы сможете оценить эффективность их всех.
Сортировка Шелла
Приводимый ниже алгоритм сортировки (программа 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: