Difference between revisions of "Programming:Quicksort"
From CPCWiki - THE Amstrad CPC encyclopedia!
(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> ; …') |
|||
| Line 1: | Line 1: | ||
| − | Does a Quicksort (ascending) on a memory range in | + | 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). |
<pre> | <pre> | ||
Latest revision as of 10:49, 7 February 2021
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
