Автор работы: Пользователь скрыл имя, 24 Апреля 2013 в 18:42, курсовая работа
Мова асемблера будь-якого процесора суттєво складніша будь-якої мови високого рівня. Щоб скористатись всіма можливостями мови асемблера, треба по крайній мірі знати команди мікропроцесора, а їх число з усіма можливими варіантами переважає 100, їх кількість значно перевищує кількість операторів і ключових слів інших мов високого рівня. Проблема ускладнюється ще тим, що зміни в асемблері виникають набагато швидше ніж в мовах високого рівня, це зв’язано з появою нових мікропроцесорів і відповідно нових команд.
ВСТУП 5
Розділ 1 Теоретична частина 6
1.1 Алгоритм сортування 6
1.2 Відомі варіанти сортування 7
Розділ 2 Практична частина 12
2.1 Сортування Шелла 12
2.2 Текст програми сортування Шелла 14
2.3 Графічний матеріал 18
ВИСНОВКИ 19
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 20
Єдиною характеристикою
Досить хороший варіант
При використанні таких приростів середня кількість операцій: O(nˆ7/6), у гіршому разі - порядку O(nˆ4/3). Якщо використовувати погані прирости, то складність алгоритму буде порядку O(nˆ2).
Потрібно звернути увагу на те, що послідовність обчислюється в порядку, протилежному використовуваному: inc[0]= 1, inc[1]= 5 ... Формула дає спочатку менші числа, потім все більші і більші, тоді як відстань між сортованими елементами, навпаки, повинна зменшуватися. Тому масив приростів inc обчислюється перед запуском власне сортування до максимальної відстані між елементами, яка буде першим кроком в сортуванні Шелла. Потім його значення використовуються в зворотному порядку.
Сортування Шелла названо
Незважаючи на те, що сортування Шелла в багатьох випадках повільніше, ніж швидке сортування, вона має ряд переваг:
- відсутність потреби в пам'яті під стек;
- відсутність деградації при невдалих наборах даних - швидке сортування легко деградує до 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- Результат роботи програми
ВИСНОВКИ
Програмно реалізовано сортування масиву за допомогою алгоритму Шелла. Сортування Шелла - алгоритм сортування, що є вдосконаленим варіантом сортування вставками. Ідея методу Шелла полягає в порівнянні елементів, що стоять не тільки поруч, але і на певній відстані один від одного.
Єдиною характеристикою сортування Шелла є приріст - відстань між сортованими елементами. В кінці приріст завжди рівний одиниці – метод завершується звичайним сортуванням вставками, але саме послідовність приростів визначає зростання ефективності.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
Информация о работе Реалізація на асемблері алгоритму сортування Шелла