quicksort in assembly 
Author Message
 quicksort 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 implementation

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. quicksort implementation in assembly

2. Quicksort quickie

3. QuickSort(), native code, Force compiler

4. QUICKSORT and SHELLSORT

5. Data sturctures and quicksort

6. quicksort in Haskell

7. elegance vs efficiency (quicksort)

8. QuickSort function?

9. Quicksort vs. Heapsort

10. Heapsort vs. Quicksort

11. Improved quicksort

12. Test8 quicksort

 

 
Powered by phpBB® Forum Software