home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 December / simtel1292_SIMTEL_1292_Walnut_Creek.iso / msdos / pcmag / vol7n16.arc / QSORTI.ASM < prev    next >
Assembly Source File  |  1988-09-27  |  3KB  |  116 lines
  1.         name    qsorti
  2.         title   QSORTI.ASM Integer QuickSort
  3.         page    55,132
  4. ;
  5. ; QSORTI.ASM --- Integer Quicksort
  6. ;
  7. ; Copyright 1988, Ziff Communications Co.
  8. ; PC Magazine * Ray Duncan
  9. ;
  10. ; Call with:    DS:SI = address of first item to sort
  11. ;               DS:DI = address of last item to sort
  12. ;               Assumes items are 2-byte integers
  13. ;
  14. ; Returns:      Nothing, all registers unchanged.
  15. ;
  16.  
  17. itemsiz equ     2               ; bytes per integer
  18.  
  19. _TEXT   segment word public 'CODE'
  20.  
  21.         assume  cs:_TEXT,ds:NOTHING,es:NOTHING
  22.  
  23.                                 ; stack variables       
  24. left    equ     [bp-8]          ; first item to sort
  25. right   equ     [bp-4]          ; last item to sort
  26.  
  27.         public  qsorti          ; make visible to Linker
  28.  
  29. qsorti  proc    near
  30.  
  31.         cmp     di,si           ; if right <= left
  32.         jna     qsort5          ; just exit
  33.  
  34.         push    bp              ; set up stack frame
  35.         mov     bp,sp           ; and local variables
  36.         push    es              
  37.         push    di              ; offset last item
  38.         push    ds
  39.         push    si              ; offset first item
  40.         push    dx
  41.         push    cx
  42.         push    bx
  43.         push    ax      
  44.         
  45.         sub     si,itemsiz      ; SI = i = left - 1
  46.                                 ; DI = j = right
  47.         mov     bx,di           ; BX = right
  48.  
  49. qsort1:                         ; partition array on
  50.                                 ; value of rightmost item
  51.  
  52. qsort2:                         ; scan right for item
  53.                                 ; >= partitioning value
  54.  
  55.         add     si,itemsiz      ; i++
  56.  
  57.         mov     ax,[si]         ; while(items[i] < items[right])
  58.         cmp     ax,[bx]         ; (guaranteed to terminate
  59.         jl      qsort2          ;  when i = right)
  60.  
  61. qsort3:                         ; scan left for item
  62.                                 ; <= partitioning value
  63.  
  64.         sub     di,itemsiz      ; j--
  65.  
  66.         cmp     di,left         ; while(items[j] > items[right]
  67.         jna     qsort4          ; && (j > left)
  68.         mov     ax,[di]
  69.         cmp     ax,[bx]
  70.         jg      qsort3
  71.  
  72. qsort4: mov     ax,[di]         ; exchange the items
  73.         xchg    ax,[si]
  74.         mov     [di],ax
  75.  
  76.         cmp     di,si           ; while(j > i)
  77.         ja      qsort1          ; (do until pointers cross)
  78.  
  79.         mov     ax,[di]         ; undo the last exchange
  80.         xchg    ax,[si]
  81.         mov     [di],ax
  82.  
  83.         mov     ax,[bx]         ; put the partitioning
  84.         xchg    ax,[si]         ; element into position
  85.         mov     [bx],ax
  86.  
  87.         push    si              ; save i
  88.  
  89.         mov     di,si           ; qsort(left, i-1)
  90.         sub     di,itemsiz
  91.         mov     si,left
  92.         call    qsorti
  93.         
  94.         pop     si              ; qsort(i+1, right)
  95.         add     si,itemsiz
  96.         mov     di,right
  97.         call    qsorti
  98.  
  99.         pop     ax              ; restore registers,
  100.         pop     bx              ; discard stack frame
  101.         pop     cx
  102.         pop     dx
  103.         pop     si
  104.         pop     ds
  105.         pop     di
  106.         pop     es
  107.         pop     bp
  108.  
  109. qsort5: ret                     ; return to caller
  110.  
  111. qsorti  endp
  112.  
  113. _TEXT   ends
  114.  
  115.         end
  116.