Category:Z80 Routines:Data:Quicksort

Description

This code snippet sorts a list using quicksort algorithm. To know about this algorithm read [Quicksort in Wikipedia]

Code

Note: sorts 1 byte numbers, it needs adaptation for real situation use.

;
; >>> Quicksort routine v1.1 <<<
; by Frank Yaul 7/14/04
;
; 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
;
; >>> end Quicksort <<<
;
 

source: [[1]]