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

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]. Но у него используется понятие медианы последовательности. Задачу нахождения медианы мы рассматривали выше. Эта задача интересна еще и тем, что она, по сути, является одной из задач поиска, рассмотрению которых посвящен следующий раздел.