Сборник по задачам и примерам Assembler


Сортировка массивов - часть 7


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=<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:

Сортировка с помощью дерева

Следующий алгоритм (программа prgl0_229.asm) является улучшением сортировки прямым выбором. Автор алгоритма сортировки с помощью дерева — Дж. У. Дж. Уильяме (1964 год). В литературе этот алгоритм носит название «пирамидальной» сортировки. Если обсужденные выше сортировки интуитивно понятны, то алгоритм данной сортировки необходимо пояснить подробнее. Этот алгоритм предназначен для сортировки последовательности чисел, которые являются отображением в памяти дерева специальной структуры — пирамиды. Пирамида — помеченное корневое двоичное дерево заданной высоты h, обладающее тремя свойствами:




- Начало -  - Назад -  - Вперед -



Книжный магазин