Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективний, адже він сортує “на місці", тобто він не потребує додаткових масивів. Крім того, цей алгоритм оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C (n) та M (n) він має складність O (n log2 n), але містить складний елемент в умові. Тобто, в умові A [left] має бути строго менше ніж x, а A [right] - строго більше за x. Якщо ж замість “строго більше” та “строго менше" поставити знаки, що позначають “більше, або дорівнює” та “менше, або дорівнює", то індекси left і right пробіжать увесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхом ускладнення умов продовження перегляду, але це б погіршило ефективність програми.
Отже, головною задачею, яку має вирішити людина, яка повинна розв’язати задачу сортування - це визначення як позитивних, так і усіх негативних характеристик різних алгоритмів сортування, передбачення кінцевого результату. До того ж, треба враховувати головне - чи, можливо, цю задачу задовольнить один з класичних простих алгоритмів сортування.
1. Львов М.С., Співаковський О.В. Основи алгоритмізації та програмування. - Херсон, 1997.
2. Д. Кнут. Искусство программирования ЭВМ: Т.3. Сортировка и поиск. М., МИР, 1978.
.286
. model tiny
. code
org 100h
start:
jmp begin
n db?
a db 0,255 dup (?)
; si=i; di=j
conswap proc near
pusha
mov al,byte ptr a [si]
mov bl,byte ptr a [di]
cmp al,bl
jae con_sk
mov byte ptr a [si],bl
mov byte ptr a [di],al
con_sk:
popa
retn
conswap endp
conflict proc near
push bp
mov bp,sp
pusha
mov ax, [bp+4] ; i
mov bx, [bp+6] ; k
; j=dx
mov dx,ax
shl dx,1; j=i*2
cmp dx,bx
ja conf_stop; j>k
cmp dx,bx
jb conf_1
; j=k
; conswap (i,j)
mov si,ax
mov di,dx
call conswap
jmp conf_stop
; j<k
conf_1:
push ax
mov si,dx
mov ah,byte ptr a [si+1]
mov al,byte ptr a [si]
cmp ah,al
jbe sk_2
inc dx
sk_2:
pop ax
; if (a [j+1] >a [j]) j++;
; conswap (i,j)
mov si,ax
mov di,dx
call conswap
; conflict (j,k);
push bx
push dx
call conflict
pop dx
pop bx
conf_stop:
popa
pop bp
retn
conflict endp
sorttree proc near
push bp
mov bp,sp
pusha
mov ax, [bp+4] ; i
mov bl,n
xor bh,bh; n
shr bx,1
cmp ax,bx; i<n
jae sort_exit
; sorttree (2*i)
mov bx,ax
shl bx,1
push bx
call sorttree
pop bx
; sorttree (2*i)
mov bx,ax
shl bx,1
inc bx
push bx
call sorttree
pop bx
; conflict (i,n)
mov bl,n
xor bh,bh
push bx
push ax
call conflict
pop ax
pop bx
sort_exit:
popa
pop bp
retn
sorttree endp
start_sort proc
mov ax,1
push ax
call sorttree
pop ax
mov cl,n
mov ch,0
inc cx
lo:
; conswap (k,1)
mov si,cx
mov di,1
call conswap
; conflict (1,k-1)
mov bx,cx
dec bx
push bx
push ax
call conflict
pop ax
pop bx
dec cx
cmp cx,1
jne lo
ret
start_sort endp
in_file db 'piramid. dat',0
out_file db 'piramid. out',0
errm db 'File error$'
begin:
; вiдкрити вхiдний файл
mov ah,3dh
mov al,0
mov dx,offset in_file
int 21h
jc err_file
mov si,ax; handle
; read
mov ah,3fh
mov bx,si
mov cx,255
mov dx,offset a+1
int 21h
mov n,al
; close
mov ah,3eh
mov bx,si
int 21h
call start_sort
; creat
mov ah,3ch
xor cx,cx
mov dx,offset out_file
int 21h
mov si,ax
; write
mov ah,40h
mov bx,si
mov cl,n
mov ch,0
mov dx,offset a+1
int 21h
; close
mov ah,3eh
mov bx,si
int 21h
. exit 0
err_file:
mov ah,9
mov dx,offset errm
int 21h
. exit 0
end start