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

Сортировка массивов - часть 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, целью которых является проверка выполнения следующих неравенств:

  • 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-l — 1 :=j+1; перейти на шаг q2;

  • j-1>M>r-j — г:=j-1; перейти на шаг q2.

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

    Рисунок 2.4. Последовательность сравнений шага q7

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

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




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