Last modified on 7 February 2021, at 10:49

Programming:Quicksort

Revision as of 10:49, 7 February 2021 by Litwr (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Does a Quicksort (ascending) on a memory range in 67 bytes. An optimization for space is possible if you replace the absolute jumps with relative jumps (saves 6 bytes).

;
; Usage: bc->first, de->last,
; call qsort
; Destroys: abcdefhl
;
qsort   ld      hl,0
        push    hl
qsloop  ld      h,b
        ld      l,c
        or      a
        sbc     hl,de
        jp      c,next1 ;loop until lo<hi
        pop     bc
        ld      a,b
        or      c
        ret     z       ;bottom of stack
        pop     de
        jp      qsloop
next1   push    de      ;save hi,lo
        push    bc
        ld      a,(bc)  ;pivot
        ld      h,a
        dec     bc
        inc     de
fleft   inc     bc      ;do i++ while cur<piv
        ld      a,(bc)
        cp      h
        jp      c,fleft
fright  dec     de      ;do i-- while cur>piv
        ld      a,(de)
        ld      l,a
        ld      a,h
        cp      l
        jp      c,fright
        push    hl      ;save pivot
        ld      h,d     ;exit if lo>hi
        ld      l,e
        or      a
        sbc     hl,bc
        jp      c,next2
        ld      a,(bc)  ;swap (bc),(de)
        ld      h,a
        ld      a,(de)
        ld      (bc),a
        ld      a,h
        ld      (de),a
        pop     hl      ;restore pivot
        jp      fleft
next2   pop     hl      ;restore pivot
        pop     hl      ;pop lo
        push    bc      ;stack=left-hi
        ld      b,h
        ld      c,l     ;bc=lo,de=right
        jp      qsloop