Форум программистов [Powered by Invision Power Board]

Код

global _main
extern _printf
extern _scanf
extern _getch

BITS 32

segment .stack use 32
stack times 1000 db 0

segment .data use32
mas db 12,42,23,62,21,34,63      
x db 0              ; временная переменная
i dw 0
l dw 0
m dw 0
j dw 0
k dw 0

segment .code use32

;процедура insert_item_in_tree(i, mas, N)
_insert_item_in_tree:
    push si
    push cx
    mov j, si      ; j := i
@@m4:    mov si, j      ; j -> si
    mov ax, j      ; k := 2*j; l := k+1
    shl ax, 1      ; j*2
    mov k, ax      ; k := j*2
    inc ax
    mov l, ax      ; l := k+1
    cmp ax, m      ; l < m?
    ja @@m2
    mov al, mas[si-1] ; ax := mas[j]
    mov di, k
    cmp al, mas[di-1]
    jna @@m6
    inc di
    cmp al, mas[di-1]
    jna @@m6
    jmp @@m2
; условие выполнилось:
; 2j+1 =< M AND (mas[j] < mas[2j] OR mas[j] < mas[2j+1])
; обмен с mas[j]
@@m6:    mov di, k
    mov al, mas [di-1] ; ax := mas[k]
    inc di
    cmp al, mas[di-1]  ; mas[k] > mas[l]?
    jna @@m3
    mov al, mas[si-1]
    mov x, al       ; x := mas[j]
    dec di
    mov al, mas[di-1]
    mov mas[si-1], al  ; mas[j] := mas[k]
    mov j, di       ; j := k
    mov al, x
    mov mas[di-1], al  ; mas[k] := x
    jmp @@m4
; @@m3: x := mas[j] перейти на @@m1
@@m3:    mov al, mas[si-1]  ; mas[k] <= mas[l]
    mov x, al       ; x := mas[j]
    mov al, mas[di-1]
    mov mas[si-1], al  ; mas[j] := mas[l]
    mov j, di       ; j := l
    mov al, x
    mov mas[di-1], al
    jmp @@m4
; условие выполнилось:
; 2j+1 =< M AND (mas[j] < mas[2j] OR mas[j] < mas[2j+1])
@@m2:    mov ax, k
    cmp ax, m
    jne @@m1
    mov di, k
    mov al, mas[di-1]  ; al := mas[k]
    cmp mas[si-1], al  ; mas[j] < mas[k]?
    jae @@m1
    mov al, mas[si-1]
    mov x, al
    mov di, n
    mov al, mas[di-1]
    mov mas[si-1], al  ; mas[j] := mas[n]
    mov al, x
    mov mas[di-1], al  ; mas[n] := x
@@m1:    pop cx
    pop si
    ret
ret

_main:
    ;...
    mov ax, n       ; n-1
    mov m, ax       ; m := n
    shr ax, 1
    mov i, ax       ; i := n/2
    mov l, ax       ; l := i
; строим пирамиду на основе входного массива:
    mov cx, l       ; цикл по k := 1..l
    mov si, i
@@cycl1:mov i, si
    call _insert_item_in_tree
    dec si           ; i := i-1
    loop @@cycl1
; а теперь собственно сортировка:
    mov cx, n-1       ; n-2
@@cycl2:xor si, si
    mov al, mas[si]
    mov x, al
    mov di, m
    mov al, mas[di-1]
    mov mas[si], al       ; mas[1] := mas[m]
    mov al, x
    mov mas[di-1], al  ; mas[m] := x
    dec m
    inc si           ; i := 1
    call _insert_item_in_tree
    loop @@cycl2
    ;...
ret