home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / C / MAXONC3_6OF8.DMS / in.adf / LIBSRC.LHA / LIBSRC / quicksort.asm < prev    next >
Encoding:
Assembly Source File  |  1994-02-12  |  2.2 KB  |  101 lines
  1.  
  2.     ; Himpelsoft C++ Project:
  3.     ; Library-Modul "quicksort"
  4.     ; Jens Gelhar 11.02.94
  5.  
  6.     xdef _qsort,qsort__PvUiUiPFiPCvPCvp
  7.  
  8.     xref uintmult
  9.  
  10. _qsort:
  11. qsort__PvUiUiPFiPCvPCvp:
  12.     ; Stack-Parameter: 0 Zeiger auf Vector
  13.     ;                  4 Elementanzahl
  14.     ;                  8 Elementgroesse
  15.     ;                 12 Vergleichsfunktion
  16.     movem.l    d2/d3/a2/a6,-(a7)
  17.     move.l     20+0(a7),a0    ; Zeiger auf Vector
  18.     move.l    20+4(a7),d3    ; Elementanzahl
  19.     move.l    20+8(a7),d2    ; Elementgröße
  20.     move.l    20+12(a7),a6    ; Vergleichsfunktion
  21.     cmp.l    #1,d2
  22.     beq.b    .1
  23.     blo.b    .pop
  24.     addq.l    #1,d2
  25.     and.w    #$FFFE,d2    ; Word-Alignment
  26. .1    move.l    d3,d1
  27.     move.l    d2,d0
  28.     jsr    uintmult
  29.     add.l    a0,d0
  30.     sub.l    d2,d0
  31.     move.l    d0,a1        ; Vectorende (letztes Element) nach a1
  32.     bsr.b    qsrek
  33. .pop    movem.l    (a7)+,d2/d3/a2/a6
  34.     rts
  35.  
  36. qsrek:    ; Rekursion: von a0 bis einschl. a1 d3 Elemente der Groesse d2, Vergleichen mit a6
  37.     cmp.l    a1,a0
  38.     bhs.b    .ret        ; Vector leer bzw. nur ein Element
  39.  
  40.     move.l    d3,d1
  41.     lsr.l    #1,d1
  42.     move.l    d2,d0
  43.     jsr    uintmult
  44.     add.l    a0,d0
  45.     move.l    d0,a2        ; Vectormitte
  46.     bsr.b    qswap        ; Vergleichselement an erste Stelle
  47.     move.l    a0,a2        ; "last" nach a2
  48.     move.l    d3,-(a7)    ; Anzahl merken
  49.     move.l    a0,-(a7)    ; Anfang merken
  50.     add.l    d2,a0        ; erstes Element überspringen
  51.     moveq    #0,d3        ; d3: Index von "last"
  52. .loop    cmp.l    a1,a0
  53.     bhi.b    .end
  54.     ; Vergleichen:
  55.     movem.l    a0/a1,-(a7)
  56.     move.l    8(a7),-(a7)
  57.     move.l    a0,-(a7)
  58.     jsr    (a6)
  59.     addq.l    #8,a7
  60.     movem.l    (a7)+,a0/a1
  61.     tst.l    d0
  62.     bpl.b    .next
  63.     add.l    d2,a2        ; "last"-Zeiger weitersetzen
  64.     addq.l    #1,d3
  65.     bsr.b    qswap        ; vertauschen
  66. .next    add.l    d2,a0
  67.     bra.b    .loop
  68. .end    ; Schleifenende
  69.     move.l (a7)+,a0         ; Anfangszeiger
  70.     bsr.b qswap             ; Vergleichselement zurücktauschen
  71.     ; erste Rekursion:
  72.     movem.l    d3/a1/a2,-(a7)
  73.     move.l    a2,a1        ; neuer Endzeiger:
  74.     sub.l    d2,a1
  75.     bsr.b    qsrek        ; übrige Parameter stimmen schon
  76.     ; zweite Rekursion:
  77.     movem.l    (a7)+,d0/a1/a2
  78.     move.l    a2,a0
  79.     add.l    d2,a0        ; Mitte+1 = neuer Anfang
  80.     move.l    (a7)+,d3    ; Gesamtanzahl
  81.     sub.l    d0,d3
  82.     subq.l    #1,d3        ; Anzahl
  83.     bra.b    qsrek        ; und wieder absteigen
  84. .ret    rts
  85.  
  86. qswap:    ; Elemente a0 und a2 vertauschen, Seiteneffekt auf d0 und d1
  87.     cmp.l    a0,a2
  88.     beq.b    .0
  89.     move.l    d2,d0
  90.     add.l    d2,a0
  91.     add.l    d2,a2
  92. .loop    move.b    -(a0),d1
  93.     move.b    -(a2),(a0)
  94.     move.b    d1,(a2)
  95.     subq.l    #1,d0
  96.     bhi.b    .loop
  97. .0    rts
  98.  
  99.     end
  100.  
  101.