Changes
Created page with 'Does a Quicksort (ascending) on a memory range in 44 bytes. An optimization for space is possible if you replace the absolute jumps with relative jumps (saves 6 bytes). <pre> ; …'
Does a Quicksort (ascending) on a memory range in 44 bytes. An optimization for space is possible if you replace the absolute jumps with relative jumps (saves 6 bytes).
<pre>
;
; 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
</pre>
[[Category:Programming]]
<pre>
;
; 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
</pre>
[[Category:Programming]]
