quicksort implementation in assembly 
Author Message
 quicksort implementation in assembly

hi folks,

i've written a quicksort in assembly.  would be glad to
receive any pointers on how i could have made it better.

;;; quicksort implementationjmp start
==========================================================

jmp start

DAT     dw      48, 16, 9, 30, 4, 1, 25, 3, 2, 7, 41, 2, 0
SZ      equ     13

start:
    mov bp, SZ
    dec bp
    mov bx, 0
    push bp     ; top
    push bx     ; bottom
    call qsort

    mov ah, 4ch
    int 21h

;;; passing parameters via stack
;;; order on stack - lower bound, then upper bound
qsort   proc
    push bx
    push bp
    mov bp, sp
    mov bx, [bp + 6]    ; get lower bound
    mov bp, [bp + 8]    ; get upper bound

;; terminating condition
    cmp bx, bp          ; if anchors crossover, we are done
    jge done
    call partition
    push di              ; save pivot for second qsort call

;; low end of the array
    dec di              ; exclude pivot - already sorted
    push di             ; store upper bound
    push bx             ; store lower bound
    call qsort
    pop di              ; get back stored pivot

;; high end of the array
    inc di              ; exclude pivot - already sorted
    push bp             ; store upper bound
    push di             ; store lower bound
    call qsort
done:
    pop bp
    pop bx
    ret 4
qsort   endp

;;; place values that are smaller than pivot on left side
;;; and larger than pivot on right.
partition  proc
    push bx
    push bp
    push cx
    push si
    push dx

;; adjust size of pointer according to data type
    shl bx, 1     ; multiple by 2 to access word
    shl bp, 1
    lea si, DAT   ; make SI point to our array
    mov dx, si    ; save first location
    add dx, bx
    mov cx, [si + bx]   ; take first item as pivot value
    add bp, 2           ; compensate for the initial dec BP
up:
    add bx, 2
    cmp [si + bx], cx
    jb  up
down:
    sub bp, 2
    cmp [si + bp], cx
    jg  down

    cmp bx, bp          ; two end pointers crossover?
    jge crossed

;; swap values pointed by 'bx' (moving up);; and 'bp' (coming down)
    xchg    [si + bx], [si + bp]
    jb  up

crossed:
;; swap value pointed by 'down' index with [pivot]
    mov bx, dx
    xchg [si + bp], [bx]

;; convert it back to data-type independence positions
    shr bp, 1
    mov di, bp  ; set pivot to be 'down' index

    pop dx
    pop si
    pop cx
    pop bp
    pop bx
    ret
partition endp
    end

================================================================

Sent via Deja.com http://www.*-*-*.com/
Share what you know. Learn what you don't.



Sat, 12 Jan 2002 03:00:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Just fo fun: a minimal implementation of QuickSort

2. quicksort in assembly

3. Assembly Language Implementation

4. OOP implementation in assembly language?

5. x86 assembly implementation of Mandelbrot Set

6. Quicksort quickie

7. QuickSort(), native code, Force compiler

8. QUICKSORT and SHELLSORT

9. Data sturctures and quicksort

10. quicksort in Haskell

11. elegance vs efficiency (quicksort)

12. QuickSort function?

 

 
Powered by phpBB® Forum Software