Сборник по задачам и примерам Assembler
jmpq2 q8: извлекаем из стека
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, целью которых является проверка выполнения следующих неравенств:
Проверка этих неравенств реализуется в виде попарных сравнений, последовательность которых выглядит так, как показано на Рисунок 2.4.
Рисунок 2.4. Последовательность сравнений шага q7
За подробностями алгоритма можно обратиться к тому 3 «Сортировка и поиск» книги Кнута .
Сушествует другой вариант алгоритма этой сортировки — у Вирта в книге «Алгоритмы + структуры данных - программы» [4]. Но у него используется понятие медианы последовательности. Задачу нахождения медианы мы рассматривали выше. Эта задача интересна еще и тем, что она, по сути, является одной из задач поиска, рассмотрению которых посвящен следующий раздел.
