I have implemented several sorting algorithms for the Z80. It is a github project (https://github.com/litwr2/Z80-sorting). IMHO we did not have a proper quicksort implementation for the Z80 until now. I know that we have one (http://www.cpcwiki.eu/index.php/Programming:Quicksort) on a cpcwiki page but it is for bytes only and it doesn't check possible stack overflow which makes it dangerous to use.
I have also implemented (https://github.com/litwr2/6502-sorting) the same algos for the 6502. It is interesting that the Z80 shows that it needs only 1.7-2 times more clock ticks than the 6502.
Does anybody knows about other implementations of fast sort algos for the Z80?
It would be also great if somebody can find ways to make these implementations more faster. :)
I'm not sure about fast or faster, but here ya go:
https://wikiti.brandonw.net/index.php?title=Category:Z80_Routines:Data:Quicksort
;TI86 Z80 Quicksort Implementation
;by Frank Yaul 7/14/04
#include "ti86asm.inc"
.org _asm_exec_ram
ld b,59
ld hl,list
rand:
ld a,r
ld c,a
add a,a
add a,a
add a,c
and %00011111
add a,65
ld (hl),a
inc hl
djnz rand
ld hl,list
call _puts
call _newline
ld bc,list
ld de,list+59
call qsort
ld hl,list
call _puts
ret
list: .db "AAAAAAAAAAAAAAAAAAAA",
.db "AAAAAAAAAAAAAAAAAAAA",
.db "AAAAAAAAAAAAAAAAAAAA",0
;
; >>> Quicksort routine v1.0 <<<
;
; by Frank Yaul 7/14/04
; Under GPL License
;
; Usage: bc=first elem index
; de=last elem index
;
; Destroys: abcdefhl
;
qsort:
ld hl,0
push hl
quicksort:
ld h,b
ld l,c
scf
ccf
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 quicksort
next1:
push de
push bc
ld a,(bc)
ld h,a ;pivot
dec bc
inc de
fromleft: ;do i++ while cur<piv
inc bc
ld a,(bc)
cp h
jp c,fromleft
fromright: ;do i-- while cur>piv
dec de
ld a,(de)
ld l,a
ld a,h
cp l
jp c,fromright
push hl ;save pivot
ld h,d
ld l,e
scf
ccf
sbc hl,bc
jp c,next ;exit if lo>hi
ld a,(bc)
ld h,a
ld a,(de)
ld (bc),a
ld a,h
ld (de),a ;swap
pop hl ;restore pivot
jp fromleft
next:
pop hl ;restore pivot
pop hl ;pop lo
push bc ;stack=left-hi
ld b,h
ld c,l ;bc=lo,de=right
jp quicksort
;
; >>> end Quicksort <<<
;
.end
Quote from: SRS on 17:13, 07 February 21
I'm not sure about fast or faster, but here ya go:
https://wikiti.brandonw.net/index.php?title=Category:Z80_Routines:Data:Quicksort (https://wikiti.brandonw.net/index.php?title=Category:Z80_Routines:Data:Quicksort)
;TI86 Z80 Quicksort Implementation
;by Frank Yaul 7/14/04
.end
Thank you but your link and quote point to the same routine as in CPCwiki.