Реалізація на асемблері алгоритму сортування Шелла

Єдиною характеристикою сортування Шелла є приріст - відстань між сортованими елементами. В кінці приріст завжди рівний одиниці – метод завершується звичайним сортуванням вставками, але саме послідовність приростів визначає зростання ефективності.

 

Досить хороший варіант запропонував Р.Седжвік. Його послідовність приростів має такий вигляд:

При використанні таких приростів  середня кількість операцій: O(nˆ7/6), у гіршому разі - порядку O(nˆ4/3). Якщо використовувати погані прирости, то складність алгоритму буде порядку O(nˆ2).

Потрібно звернути увагу на те, що послідовність обчислюється в порядку, протилежному використовуваному: inc[0]= 1, inc[1]= 5 ... Формула дає спочатку менші числа, потім все більші і більші, тоді як відстань між сортованими елементами, навпаки, повинна зменшуватися. Тому масив приростів inc обчислюється перед запуском власне сортування до максимальної відстані між елементами, яка буде першим кроком в сортуванні Шелла. Потім його значення використовуються в зворотному порядку.

Сортування Шелла названо начесть  автора — Дональда Шелла, який опублікував цей алгоритм у 1959[1] році. В деяких пізніших друкованих виданнях алгоритм називають сортуванням Шелла-Мацнера, за ім'ям Нортона Мацнера. Але сам Мацнер стверджував: «Мені не довелось нічого робити з цим алгоритмом, і моє ім'я не має пов'язуватись з ним».

Незважаючи на те, що сортування Шелла  в багатьох випадках повільніше, ніж  швидке сортування, вона має ряд  переваг:

- відсутність потреби в пам'яті під стек;

- відсутність деградації при невдалих наборах даних - швидке сортування легко деградує до O (n ²), що гірше, ніж найгірше гарантований час для сортування Шелла.

 

 

2.2 Текст програми сортування Шелла

.model small

.stack 100h

.data

mas          db 0,6,5,8,9,1,4,2,7,3

n=$-mas

mes1 db 'Ishodniy massiv: ','$'

mes2 db 'Vihodnoy massiv: ','$'

x            db   0

mas_dist     db   7,5,3,1

t=$-mas_dist

 

.code

start:

mov ax,@data

mov ds,ax

mov es,ax

 

mov ah,09h

lea dx,mes1

int 21h

mov cx,10

mov si,0

mov dx,0

 

in1:

mov ah,02h

mov dl,mas[si]

add dx,30h

int 21h

mov dx,20h

int 21h

inc si

loop in1

mov dx,0ah

int 21h

mov dx,0dh

int 21h

 

xor bx,bx

d1:

                mov cx,t

                mov si,0

@@d2:

     push cx

             mov bl, mas_dist[si]

             inc si

             push si

             mov  di,bx

@@d3: 

    cmp di,n-1

            ja m1

            mov si,di

            sub si,bx

            mov al,mas[di] 

            mov x,al

@@d4:       mov al,x

            cmp al,mas[si]

            jae @@d6

            push di

            push si

            pop di

            add di,bx

            mov al,mas[si]

            mov mas[di],al

            pop di

            sub si,bx

            cmp si,0

            jge @@d4

@@d6:       push di

            push si

            pop di

            add di,bx

            mov al,x

            mov mas[di],al

            pop di

            inc di

jmp @@d3

m1: pop si

pop cx

loop @@d2

 

exit:

mov ah,09h

lea dx,mes2

int 21h

mov cx,10

mov si,0

mov dx,0

 

out1:

mov ah,02h

mov dl,mas[si]

add dx,30h

int 21h

mov dx,20h

int 21h

inc si

loop out1

 

mov ah,0ah

int 21h

mov ah,0dh

int 21h

 

mov ax,4c00h

int 21h

end start

 

 

2.3 Графічний матеріал

Рисунок 1- Результат роботи програми

 

 

ВИСНОВКИ

Програмно реалізовано сортування масиву за допомогою алгоритму Шелла. Сортування Шелла - алгоритм сортування, що є вдосконаленим варіантом сортування вставками. Ідея методу Шелла полягає в порівнянні елементів, що стоять не тільки поруч, але і на певній відстані один від одного.

 Єдиною характеристикою сортування Шелла є приріст - відстань між сортованими елементами. В кінці приріст завжди рівний одиниці – метод завершується звичайним сортуванням вставками, але саме послідовність приростів визначає зростання ефективності.

 

 

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Фролов А.В., Фролов Г.В. "Операционная система MS-DOS" в трех томах. Москва, "Диалог МИФИ", 1992 год.
2. Практическая работа на компьютерах семейства IBM PC в операционной среде MS DOS. Учебное пособие. Москва, "Диалог МИФИ" , 1995 год.
3. Том Сван Т. "Освоение Turbo Assembler"."Диалектика", Киев, 1996 год
4. "Освоение Turbo Assembler"."Диалектика", Киев, 1996 год.
5. Рудаков П.И., Финогенов К.Г. “Язык ассемблера: уроки программирования” “Диалог-МИФИ”, Москва,2001г.
6. Кулаков В.“Программирование на аппаратном уровне. Специальный справочник”.Второе издание, “Питер”, С.-Петербург, 2003 г.
7. Методичні вказівки до виконання курсових робіт з курсу «Системне програмування» для студентів всіх форм навчання спеціальностей 6.091500 «Спеціалізовані комп’ютерні системи» та «Системне програмування»
8. Дж.Просиз. "Управление памятью в DOS"
9. "Мир", СК Ферлаг Интернешнл, Москва,1994 год.
10. Джон М.Гудмэн. "Управление памятью для всех" "Диалектика", Киев, 1995 год.
11. Юров В. Assembler.СПб.: Питер, 2001.-624с.