home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / PCMAG / VOL7N17.ARC / PP717.ARC / QSORT.ASM next >
Encoding:
Assembly Source File  |  1988-08-30  |  5.4 KB  |  160 lines
  1. ;----------------------------------------------------------------------
  2. ; QSORT.ASM --- General Purpose QuickSort
  3. ; Copyright (c) 1988 Ziff Communications Co.
  4. ; PC Magazine * Ray Duncan * 12-13-88
  5. ;----------------------------------------------------------------------
  6. ; Call with:    DS:SI = address of first item to sort
  7. ;               DS:DI = address of last item to sort
  8. ;               ES:BX = address of compare routine
  9. ;               AX    = length of each item
  10. ;
  11. ; Returns:      nothing
  12. ;
  13. ; Uses:         nothing
  14. ;
  15. ; The external compare routine must be declared as 'proc far'
  16. ; and it must accept the following parameters:
  17. ;               DS:SI = address of 1st item to compare
  18. ;               ES:DI = address of 2nd item to compare
  19. ;               CX    = length to compare
  20. ; It must return DS:SI and ES:DI unchanged and the result
  21. ; of the comparison in the CPU flags as follows:
  22. ;               Z = T        if item 1 = item 2
  23. ;               Z = F, S = T if item 1 < item 2
  24. ;               Z = F, S = F if item 1 > item 2
  25. ;----------------------------------------------------------------------
  26. _TEXT   segment word public 'CODE'
  27.         assume  cs:_TEXT,ds:NOTHING,es:NOTHING
  28.                                 ; stack variables       
  29. compare equ     dword ptr [bp-4]; address of compare routine
  30. itemsiz equ     [bp-6]          ; bytes per item
  31. left    equ     [bp-8]          ; first item to sort
  32. right   equ     [bp-10]         ; last item to sort
  33.  
  34.         public  qsort           ; make visible to Linker
  35. qsort   proc    near
  36.  
  37.         cmp     di,si           ; if right <= left
  38.         jna     qsort5          ; just exit
  39.  
  40.         push    bp              ; set up stack frame
  41.         mov     bp,sp           ; and local variables
  42.  
  43.         push    es              ; save address of 
  44.         push    bx              ; compare routine
  45.         push    ax              ; save bytes per item
  46.         push    si              ; offset first item
  47.         push    di              ; offset last item
  48.  
  49.         push    cx              ; save remaining registers
  50.         push    dx
  51.  
  52.         push    ds              ; make data addressable by
  53.         pop     es              ; ES for exchange routine
  54.  
  55.         sub     si,itemsiz      ; SI = i = left - 1
  56.                                 ; DI = right
  57.         mov     bx,di           ; BX = j = right
  58. qsort1:                         ; partition array on value of rightmost item
  59. qsort2:                         ; scan right for item >= partitioning value
  60.         add     si,itemsiz      ; i++
  61.         mov     cx,itemsiz
  62.         call    compare         ; while(items[i] < items[right])
  63.         jl      qsort2
  64.  
  65.         xchg    bx,si           ; SI = j, BX = i, DI = right
  66. qsort3:                         ; scan left for item <= partitioning value
  67.         sub     si,itemsiz      ; j--
  68.         cmp     si,left         ; while(items[j] > items[right]
  69.         jna     qsort4          ; && (j > left)
  70.         mov     cx,itemsiz
  71.         call    compare
  72.         jg      qsort3
  73.  
  74. qsort4: xchg    bx,di           ; SI = j, DI = i, BX = right
  75.  
  76.         mov     cx,itemsiz
  77.         call    exch            ; exchange the items
  78.  
  79.         xchg    si,di           ; SI = i, DI = j, BX = right
  80.         xchg    di,bx           ; SI = i, DI = right, BX = j
  81.  
  82.         cmp     bx,si           ; while(j > i)
  83.         ja      qsort1          ; (do until pointers cross)
  84.  
  85.         xchg    bx,di           ; SI = i, DI = j, BX = right
  86.         mov     cx,itemsiz
  87.         call    exch            ; undo the last exchange
  88.  
  89.         xchg    bx,di           ; SI = i, DI = right, BX = j
  90.         mov     cx,itemsiz
  91.         call    exch            ; put partitioning element into position
  92.  
  93.         push    si              ; save i
  94.  
  95.         mov     di,si           ; qsort(left, i-1)
  96.         sub     di,itemsiz
  97.         mov     si,left
  98.         les     bx,compare
  99.         mov     ax,itemsiz
  100.         call    qsort
  101.         
  102.         pop     si              ; qsort(i+1, right)
  103.         add     si,itemsiz
  104.         mov     di,right
  105.         les     bx,compare
  106.         mov     ax,itemsiz
  107.         call    qsort
  108.  
  109.         pop     dx              ; restore registers
  110.         pop     cx
  111.         pop     di
  112.         pop     si
  113.         pop     ax
  114.         pop     bx
  115.         pop     es
  116.         pop     bp
  117.  
  118. qsort5: ret                     ; return to caller
  119.  
  120. qsort   endp
  121. ;----------------------------------------------------------------------
  122. ; EXCH:         exchange two items
  123. ;
  124. ; Call with:    DS:SI = address of first item
  125. ;               DS:DI = address of second item
  126. ;               CX    = item length
  127. ;
  128. ; Returns:      nothing
  129. ;
  130. ; Uses:         AX, CX
  131. ;----------------------------------------------------------------------
  132. exch    proc    near
  133.  
  134.         cmp     cx,2            ; are items words?
  135.         jne     exch1           ; no, jump
  136.  
  137.         mov     ax,[di]         ; items are words, 
  138.         xchg    ax,[si]         ; exchange them quickly
  139.         mov     [di],ax
  140.         ret
  141.  
  142. exch1:  push    si              ; save addresses
  143.         push    di
  144.  
  145. exch2:  mov     al,[di]         ; exchange items
  146.         xchg    al,[si]         ; byte by byte
  147.         mov     [di],al
  148.         inc     si
  149.         inc     di
  150.         loop    exch2
  151.  
  152.         pop     di              ; restore addresses
  153.         pop     si
  154.         ret
  155.  
  156. exch    endp
  157.  
  158. _TEXT   ends
  159.         end
  160.