Иллюстрированный самоучитель по задачам и примерам 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
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-1 – 1: = j+1; перейти на шаг q2;
  • j-1>M>r-j – г: = j-1; перейти на шаг q2.

Проверка этих неравенств реализуется в виде попарных сравнений, последовательность которых выглядит так, как показано на рис. 2.4.

Иллюстрированный самоучитель по задачам и примерам Assembler › Сложные структуры данных › Улучшение классических методов сортировки
Рис. 2.4. Последовательность сравнений шага q7

За подробностями алгоритма можно обратиться к тому 3 "Сортировка и поиск" книги Кнута.

Существует другой вариант алгоритма этой сортировки – у Вирта в книге "Алгоритмы + структуры данных – программы" [4]. Но у него используется понятие медианы последовательности. Задачу нахождения медианы мы рассматривали выше. Эта задача интересна еще и тем, что она, по сути, является одной из задач поиска, рассмотрению которых посвящен следующий раздел.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.