圖 1 運作結果示意1
圖 2 運作結果示意2
stack segment stack
db 512 dup(?)
stack ends
data segment
arr dw 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25
;arr dw 72, 70, -38, 5, 17, -20, -89, -56, -71, 66, -54, -87, 99, 40, 59, -15, 83, 99, 24, 39, 3, -56, 20, 78, 71, 12, -7, 6, -38, 53, -71, -32, 70, -96, -98, 15, -74, 75, -94, 84, 96, -48, -35, -67, 95, -24, -29, -75, 98, -76, 17, -69, -24, 8, -24
input1 db "before sort:", 0ah, 0dh, '$'
input2 db " ", '$'
input3 db "after sort:", 0ah, 0dh, '$'
i dw ?
j dw ?
p dw 0 ;start of the array, equals to 0.
r dw 49 ;end of the array, equals to a.length - 1.
q dw ?
x dw ?
data ends
code segment
assume ds: data, cs: code, ss: stack
main:
mov ax, data
mov ds, ax
mov ax, stack
mov ss, ax
mov bx, 50
lea dx, input1
mov ah, 09h
int 21h
lea si, arr
call print_array
call linefeed
call quicksort
lea dx, input3
mov ah, 09h
int 21h
lea si, arr
call print_array
jmp done
print_array proc
; this procedure will print the elements of a given array
; input : si=offset address of the array
; : bx=size of the array
; output : none
push ax; push ax onto the stack
push cx; push cx onto the stack
push dx; push dx onto the stack
mov cx, bx ; set cx=bx
@print_array: ; loop label
mov ax, [si] ; set ax=ax+[si]
call dispsiw ; call the procedure outdec
mov ah, 2 ; set output function
mov dl, 20h ; set dl=20h
int 21h ; print a character
add si, 2 ; set si=si+2
loop @print_array ; jump to label @print_array while cx!=0
pop dx ; pop a value from stack into dx
pop cx ; pop a value from stack into cx
pop ax ; pop a value from stack into ax
ret ; return control to the calling procedure
print_array endp
;-----------------------------------------
;quicksort(a, p, r)
; if p < r
;q = quicksort(a, p, r)
;quicksort(a, p, q-1)
;quicksort(a, q+1, r)
quicksort proc
;compare p with r.
mov ax, p
cmp ax, r ;compare p with r
jge bigger1;if p ≥ r, sort is done.
;call partition(a, p, r).
call partition
;get q = partition(a, p, r).
mov q, ax
;push q+1, r into stack for later usage.
inc ax
push ax
push r
;call quicksort(a, p, q-1).
mov ax, q
mov r, ax
dec r
call quicksort
;call quicksort(a, q+1, r).
pop r
pop p
call quicksort
;when sort is done.
bigger1:
ret
quicksort endp
;-----------------------------------------
;partition(a, p, r)
; x = a[r]
; i = p - 1
; for j = p to r-1
;if a[j] ≤ x
; i = i + 1
; exchange a[i] with a[j]
; exchange a[i+1] with a[r]
; return i+1
partition proc
;get x = arr[ r ].
mov si, offset arr
mov ax, r
shl ax, 1 ;r * 2, because every counter is 2 bytes.
add si, ax
mov ax, [ si ]
mov x, ax ;x = arr[ r ].
;get i = p - 1.
mov ax, p
mov i, ax
dec i
;initialise j with p.
mov ax, p
mov j, ax
;loop j from p to r-1.
for_j:
;get arr[ j ].
mov si, offset arr
mov ax, j
shl ax, 1 ;j * 2, because every counter is 2 bytes.
add si, ax
mov ax, [ si ] ;ax = arr[ j ]
;compare a[ j ] with x.
cmp ax, x
jg bigger ;if a[ j ] > x, no swap
;get i = i + 1.
inc i
;get arr[ i ].
mov di, offset arr
mov cx, i
shl cx, 1 ;i * 2, because every counter is 2 bytes.
add di, cx
mov cx, [ di ] ;cx = arr[ i ].
;exchange arr[ i ] with arr[ j ].
mov [ di ], ax
mov [ si ], cx
;get next j.
bigger:
inc j ;j = j + 1.
mov ax, r
cmp j, ax ;compare j with r.
jl for_j ;if j ≤ r-1 continue loop.
;get arr[ i+1 ].
inc i
mov si, offset arr
mov ax, i
shl ax, 1 ;(i+1) * 2, because every counter is 2 bytes.
add si, ax
mov ax, [ si ] ;ax = arr[ i+1 ].
;get arr[ r ].
mov di, offset arr
mov cx, r
shl cx, 1 ;r * 2, because every counter is 2 bytes.
add di, cx
mov cx, [ di ] ;cx = arr[ r ].
;exchange arr[ i+1 ] with arr[ r ].
mov [ di ], ax
mov [ si ], cx
;return i+1.
mov ax, i
ret
partition endp
linefeed proc
push ax
push dx
mov dl, 0dh
mov ah, 2
int 21h
mov dl, 0ah
mov ah, 2
int 21h
pop dx
pop ax
ret
linefeed endp
dispsiw proc
push ax
push bx
push dx
test ax, ax
jnz dsiw1
mov dl, '0'
mov ah, 2
int 21h
jmp dsiw5
dsiw1:
jns dsiw2
mov bx, ax
mov dl, '-'
mov ah, 2
int 21h
mov ax, bx
neg ax
dsiw2:
mov bx, 10
push bx
dsiw3:
cmp ax, 0
jz dsiw4
xor dx, dx
div bx
add dl, 30h
push dx
jmp dsiw3
dsiw4:
pop dx
cmp dl, 10
je dsiw5
mov ah, 2
int 21h
jmp dsiw4
dsiw5:
pop dx
pop bx
pop ax
ret
dispsiw endp
done:
mov ah, 4ch
int 21h
code ends
end main