Author Topic: Quicksort and other sorts for the Z80  (Read 295 times)

0 Members and 1 Guest are viewing this topic.

Offline litwr

  • CPC6128
  • ****
  • Posts: 168
  • Country: ru
    • lidovski's www page
  • Liked: 134
  • Likes Given: 137
Quicksort and other sorts for the Z80
« on: 18:00, 07 February 21 »
I have implemented several sorting algorithms for the Z80.  It is a github project. IMHO we did not have a proper quicksort implementation for the Z80 until now.  I know that we have one 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 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. :)
« Last Edit: 18:18, 07 February 21 by litwr »

Offline SRS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 639
  • Country: de
  • Schneider CPC464 - what else ?
  • Liked: 641
  • Likes Given: 371
Re: Quicksort and other sorts for the Z80
« Reply #1 on: 18: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
Code: [Select]
;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

Offline litwr

  • CPC6128
  • ****
  • Posts: 168
  • Country: ru
    • lidovski's www page
  • Liked: 134
  • Likes Given: 137
Re: Quicksort and other sorts for the Z80
« Reply #2 on: 18:28, 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
Code: [Select]
;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.