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


       

неупорядоченная последовательность двоичных значений длиной


ПРОГРАММА 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<N TO ПЕРЕЙТИ_НА q9

1 :-1: г:=п

ВКЛЮЧИТЬ_В_СТЕК (Offffh) //Offffh - признак пустого стека q2: i :-l: j:-r+l: k:=mas[l] q3: ЕСЛИ i=<j-l TO ПЕРЕЙТИ_НА qq3

ПЕРЕЙТИ_НА q4 //итерация прекращена qq3: i:=i+l

ЕСЛИ mas[i]<K TO ПЕРЕЙТИ_НА q3 q4: j:-j-l

ЕСЛИ j<1 TO ПЕРЕЙТИ_НА q5

ЕСЛИ K<mas[j] TO ПЕРЕЙТИ_НА q4

ЕСЛИ j>i TO ПЕРЕЙТИ_НА q6

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=<j jleqq3

dec si :сохраняем i=<j jmp q4 :ПЕРЕЙТИ_НА д4//итерация прекращена qq3: moval.k ;i:=i+l

cmpmas[si].al :ЕСЛИ mas[i]<K TO ПЕРЕЙТИ_НА q3

jb q3

q4: decdi ;j:=j-l cmpdi.si :j>=i-l jb q5 mov al ,k :ЕСЛИ K<mas[j] TO ПЕРЕЙТИ_НА q4

cmp al ,mas[di]

»jb q4 q5: ;ЕСЛИ j>i TO ПЕРЕЙТИ_НА q6 cmpdi.si :j=<i ??? J9 q6 movbx.L ://обмен mas[l]:= mas[j] mov dl ,mas[bx] xchg mas[di].dl xchg mas[bx].dl jmpq7 :ПЕРЕЙТИ_НА q7 q6: mov dl.masCsi] ; mas[i]<-> 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


Содержание  Назад  Вперед