home *** CD-ROM | disk | FTP | other *** search
/ Amiga Times / AmigaTimes.iso / internet / Term / Extras / Source / term-source.lha / Glue / QuickSort.asm < prev    next >
Encoding:
Assembly Source File  |  1996-10-20  |  3.0 KB  |  174 lines
  1. ***
  2. *
  3. *    A replacement for Lattice's qsort
  4. *
  5. *    This one is a stack miser and is (hopefully) faster.
  6. *
  7. *    The algorithm is taken from:
  8. *
  9. *    Stubbs, Webre, "Data Structures with Abstract
  10. *    Data Types and Pascal" (Pacific Grove: Brooks/Cole Pub. Co
  11. *    p. 256.
  12. *
  13. *    Modifications:
  14. *
  15. *    Middle element of array is used as partition element.
  16. *    Additional logic is provided for tail recursion optimization:
  17. *    Recursive calls sort arrays at most half the size of the array
  18. *    sorted during the previous recursive call -> little stack use.
  19. *
  20. ***
  21.  
  22. COMPARE    macro
  23.     move.l    \1,a0
  24.     move.l    \2,a1
  25.     movem.l    a0/a1,-(sp)
  26.     jsr    (A3)
  27.     addq.l    #8,SP
  28.     tst.l    d0
  29.     endm
  30.  
  31.     section    text,code
  32.  
  33.     xdef    _qsort
  34.  
  35. _qsort:
  36.     movem.l D5/D4/D6/D7/A3,-(SP)
  37.     move.l    36(SP),A3
  38.     move.l    32(SP),D7
  39.     move.l    28(SP),D4    ; number of elements in array
  40.     move.l    24(SP),D5    ; bottom of array
  41.  
  42.     ; calculate size of array
  43.  
  44.     move.l    D4,D1        ; low word in right
  45.     swap    D1        ; high word in D1
  46.     mulu    D7,D4
  47.     mulu    D7,D1        ; multiply
  48.     swap    D1        ; shift high portion
  49.     clr.w    D1        ; mask high bits
  50.     add.l    D1,D4        ; add partials
  51.     sub.l    D7,D4        ; back up one
  52.     add.l    D5,D4        ; make into address
  53.  
  54.     ; calculate bit position to find middle
  55.  
  56.     moveq    #-1,D6
  57. cb0:
  58.     addq.l    #1,D6
  59.     btst    D6,D7
  60.     beq    cb0
  61.  
  62.     bsr    quick2
  63.  
  64.     movem.l (SP)+,D5/D4/D6/D7/A3
  65.     rts
  66.  
  67.     ;
  68.     ; exchange contents of A0, A1
  69.     ;
  70.  
  71. exch:
  72.     move.l    D7,D1
  73.     bra    ex1
  74. ex2:
  75.     move.b    (A0),D0
  76.     move.b    (A1),(A0)+
  77.     move.b    D0,(A1)+
  78. ex1:
  79.     dbra    D1,ex2
  80.     rts
  81.  
  82.     ; in: D5, right
  83.  
  84. quick2: movem.l D3/D2,-(SP)
  85.  
  86. quick2nr:
  87.     cmp.l    D5,D4
  88.     bls    q1        ; if left < right
  89.  
  90.     ; At this point, we wish to find middle of array
  91.     ; w/o multiplying or dividing.
  92.  
  93.     ; After finding size of array, in bytes,
  94.     ; we test hbit.     This bit will be set if we
  95.     ; are halfway between elements.
  96.  
  97.     move.l    D4,D1
  98.     sub.l    D5,D1        ; calculate size of array
  99.     btst    D6,D1
  100.     beq    q3
  101.     sub.l    D7,D1
  102. q3:
  103.     lsr.l    #1,D1        ; swap(d[left], d[mid]);
  104.     add.l    D5,D1
  105.  
  106.     move.l    D1,A0
  107.     move.l    D5,A1
  108.     bsr    exch
  109.  
  110.     COMPARE    d5,d4
  111.     ble    q2        ; if d[left] > d[right]
  112.  
  113.     move.l    D5,A0
  114.     move.l    D4,A1
  115.     bsr    exch        ; swap(d[left], d[right]);
  116. q2:
  117.     move.l    D5,D3        ; j := left
  118.     move.l    D4,D2        ; k := right
  119. q4:                ; repeat
  120.     add.l    D7,D3        ;  j := j + 1
  121.     COMPARE    d3,d5
  122.     blt    q4        ; until d[j] >= d[left]
  123. q5:
  124.     sub.l    D7,D2        ; k := k - 1
  125.     COMPARE    d2,d5
  126.     bgt    q5
  127.  
  128.     cmp.l    D3,D2
  129.     bls    q6        ; if j < k
  130.     move.l    D2,A1
  131.     move.l    D3,A0
  132.     bsr    exch        ; swap(d[j], d[k])
  133. q6:
  134.     cmp.l    D3,D2
  135.     bcc    q4        ; until j > k
  136.  
  137.     move.l    D2,A1
  138.     move.l    D5,A0
  139.     bsr    exch        ; swap(d[left], d[k])
  140.  
  141.     ; this is the recursive part.  Calculate sizes of
  142.     ; recursive calls to ensure smaller array is done
  143.     ; recursively and larger non-recursively.
  144.  
  145.     move.l    D2,D3
  146.     sub.l    D7,D2        ; k - 1
  147.     add.l    D7,D3        ; k + 1
  148.  
  149.     move.l    D2,D0
  150.     sub.l    D5,D0        ; (k - 1) - left
  151.     move.l    D4,D1
  152.     sub.l    D3,D1        ; right - (k + 1)
  153.     cmp.l    D0,D1
  154.     bge    q7
  155.  
  156.     move.l    D5,-(SP)
  157.     move.l    D3,D5
  158.     bsr    quick2        ; quick2(k + 1, right)
  159.     move.l    (SP)+,D5
  160.     move.l    D2,D4
  161.     bra    quick2nr    ; quick2(left, k - 1)
  162. q7:
  163.     move.l    D4,-(SP)
  164.     move.l    D2,D4
  165.     bsr    quick2        ; quick2(left, k - 1)
  166.     move.l    (SP)+,D4
  167.     move.l    D3,D5
  168.     bra    quick2nr    ; quick2(k + 1, right)
  169. q1:
  170.     movem.l (SP)+,D3/D2
  171.     rts
  172.  
  173.     end
  174.