MaxCoderz

for your 1 bit pleasure!

All times are UTC




Post new topic This topic is locked, you cannot edit posts or make further replies.  [ 7 posts ] 
Author Message
PostPosted: Tue 28 Jun, 2005 9:59 am 
Offline
Maxcoderz Staff
User avatar

Joined: Wed 15 Dec, 2004 7:26 pm
Posts: 2735
Location: The Hague, Netherlands
===General===
Please do not discuss in this topic. If you feel to discuss an entry, have a question or anything else open a new topic. This topic should only have this starting post, the entries and the result. All other posts will deleted. If you have question or want to discuss the entries, go to this thread.

===Description===
Simple. You'll get an array of numbers. Your task is now to sort that array from low to high (e.g.: 0,1,2,3....) without using a second array or any other thing. Or in other words, you may only use the registers af, bc, de, hl, ix and the array given. You may use the stack.

This is the array:
Code:
.db 15,3,12,0,4,6,7,15,255
As you can see the array contains random values. 255 is the 'stop' value. Your routine should be able to handle different sizes of arrays. Also there are some values, which are double.

===Conditions===
Your routine should meet the following conditions:
  • The routine may only use a, bc, de, hl, ix and the array given. The stack may be used aswell.
  • Signed and unsigned numbers are not required to be supported, but may.
  • SMC is allowed.
  • The routine should be able to handle different sizes of arrays.
  • The routine should be well documented.
  • You should state how much size your routine needs.
  • The routine should be in z80 for the TI-83(+) series.
===Deadline===
You have 4 weeks time. Until 26th of July.

===How to particpate?===
Just post your source in here if you are finished. A sample program is welcome but not required. If you update your routine, you have to edit your post, instead of posting it again. The smallest routine wins (or someone comes up with a fair system to judge both).

===Current list===

Size
15 Bytes - CoBB - swap'n'start sort
18 Bytes - Jim e - 'PHEAR MY OPTIMISING SKILLZ' sort
23 Bytes - Sigma - QBFS sort
31 Bytes - tr1p1ea - bubble sort

===Winner ===
15 Bytes - CoBB - swap'n'start sort

===Change log===
2-7-2005:
- Now there will be a winner in both size and speed :).
- Added list with current status
- Added link to the discussion.


Last edited by kv83 on Sat 20 Aug, 2005 12:34 am, edited 9 times in total.

Top
 Profile  
 
 Post subject:
PostPosted: Tue 28 Jun, 2005 3:10 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 4095
Location: I cant seem to get out of this cryogenic chamber!
Just to get things moving, note that this routine will change as its a simple bubble sort :):

Code:
SortArray:                                      ; sort array using simple bubble sort :) [31 bytes]
        ld b,1                                  ; b is our indicator
SortArrayLoop_1:
        xor a                                   ; setup indicator test
        cp b                                    ; if b is set then a switch has occured
        ret z                                   ; if no switch has occured then array is sorted
        ld b,a                                  ; reset indicator
        ld hl,Array                             ; hl holds array pointer
SortArrayLoop_2:
        ld a,(hl)                               ; get an element
        cp 255                                  ; is it our 'stop' value?
        jp z,SortArrayLoop_1                    ; if we are at the end of the array re-loop
        ld c,a                                  ; store previous in c
        inc hl                                  ; increase array pointer
        ld a,(hl)                               ; get next element
        cp c                                    ; compare with previous element
        jp nc,SortArrayLoop_2                   ; if next > previous then there is no need to switch
SortArraySwitch:
        ld (hl),c                               ; store previous in next position
        dec hl                                  ; decrease array pointer
        ld (hl),a                               ; store next in previous position
        inc hl                                  ; increase array pointer
        ld b,1                                  ; set indicator
        jp SortArrayLoop_2                      ; loop


Also i errrr never tested it, but it should work :).

Note that this is not quite a bubble sort, it is actually pretty inefficient as the number of elements is unknown, it traverses the FULL list every time *hides* :).

_________________
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image


Top
 Profile  
 
 Post subject:
PostPosted: Thu 30 Jun, 2005 7:19 pm 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
18 bytes... Image Mauhahahahaha :twisted: PHEAR MY OPTIMISING SKILLZ :twisted: :twisted:

Code:
;Sorter
;18 bytes
;
;input:
;HL = array to be sorted terminated by an indicator
;B = the stop indicator(this case 255)
;C = the Least significant element in the array
;    C=0 will always work but you could save a few clocks if you tell it
;    where to start.
;
;Output:
;sorted array :)
;
;Example:
;
; ld hl,LIST
; ld c,10       ;lowest number in list
; ld b,255      ;stop indicator
; call SORT
; ....
;LIST:
; .db 13,10,15,20,15,255
;
;NOTE: REMEMBER TO CALL SORT NOT RESTART!!!



restart:                ;DON"T CALL restart
    inc c               ;Next number to compare
    ret z               ;if it returns to zero quit
Sort:                   ; CALL SORT     <----------------------------------
    ld d,h              ;copy current location to de
    ld e,l
loop1:
    ld a,(de)           ;get element in list
    cp b                ;check if hit end of list
    jr z,restart        ;restart if done
    cp c                ;compare current number
    jr nz,noswap        ;if not noswap
    ld a,(hl)           ;swap if so
    ld (de),a
    ld (hl),c           ;c = contents of de
    inc hl              ;next place to sort into.
noswap:
    inc de              ;update compareing
    jr loop1            ;LOOP!


This method is optimised for there only being a few different elements in the array.

Edit: realised tiny optimization
Edit: another optimization(how did I miss that).
Edit: Slight change in method makes it 18 bytes(my original goal)

So sexy...Image

_________________
Image


Top
 Profile  
 
 Post subject:
PostPosted: Sat 02 Jul, 2005 8:02 am 
Offline
MCF Legend

Joined: Mon 20 Dec, 2004 8:45 am
Posts: 1601
Location: Budapest, Absurdistan
The power of swap'n'start sort!

Code:
; Sort: sorts the C terminated array at DE
; Note: the array must have at least one element before the terminator.
; Routine size: 15 bytes

Sort:
 ld h,d             ; fetch array start address
 ld l,e
Sortloop:
 ld b,(hl)          ; advance until the first inversion
 inc hl
 ld a,(hl)
 cp c
 ret z              ; bail out at the terminator
 cp b
 jr nc,Sortloop
 ld (hl),b          ; swap the offending elements
 dec hl
 ld (hl),a
 jr Sort            ; start again from the beginning :o

_________________
The Independent Z80 Assembly Guide
Acelgoyobis
PindurTI


Top
 Profile  
 
 Post subject:
PostPosted: Sun 03 Jul, 2005 10:16 am 
Offline
Maxcoderz Staff

Joined: Fri 17 Dec, 2004 5:33 pm
Posts: 790
Location: On the dark side of the moon.
The power of Gnome Sort. This is a preliminary version which hasn't been tested and is probably not complete.

[21 bytes]
Code:
;sorts the C terminated array at HL
GnomeSort:
   ld (SMArray+1),hl
SortLoop:
   ld a,(hl)
   inc hl
   ld b,(hl)
   cp c
   ret z
   cp b
   jp c,SortLoop
   jp z,SortLoop
   ;swap (b<a)
   ld (hl),a
   dec hl
   ld (hl),b
SMArray:
   ld de,array
   xor a ;ugly lower bound check
   ex de,hl
   sbc hl,de
   ex de,hl
   jp z,SortLoop
   dec hl
   jp SortLoop


EDIT: I finished it and it didn't came out to beautiful but atleast it functions.

_________________
"They say that sea was created by a man named Maarten Zwartbol, a long time ago...." - Duck, an old Corbin version


Last edited by Kozak on Sun 17 Jul, 2005 8:27 am, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Fri 08 Jul, 2005 10:15 pm 
Offline
New Member

Joined: Thu 31 Mar, 2005 10:56 pm
Posts: 27
Location: Stuck in 8-bit land.
Code:
/*
QBFS (quintessential brute-force sort) algorithm
Description:
    Sorts an array of bytes terminated by value 255.
Inputs:
    DE     Base address of array
Destroys:
    AF BC HL
Size:
    23 bytes
Notes:
    Can sort arrays with sizes in the range [0, stack space / 2]

Description:
Iterate through set of keys (0..255) in ascending order, and for each
key, iterate through array elements and push all elements matching
that key. Then, pop each element into the array in reverse order (from
high to low memory).
*/

Sort:
     XOR   A
     LD    B, A

--   LD    H, D
     LD    L, E

-    CP    (HL)
     LD    C, (HL)
     JR    NZ, +
     PUSH  AF
     INC   B
+    INC   HL
     INC   C
     JR    NZ, -
     INC   A
     JR    NZ, --

; Restore array sorted
-    DEC   HL
     POP   AF
     LD    (HL), A
     DJNZ  -
     RET

_________________
http://sigma.unitedti.org/ -- Really cool content... when I get around to uploading it.


Top
 Profile  
 
 Post subject:
PostPosted: Sat 20 Aug, 2005 12:32 am 
Offline
Maxcoderz Staff
User avatar

Joined: Wed 15 Dec, 2004 7:26 pm
Posts: 2735
Location: The Hague, Netherlands
Well,

we have a winner. Congrats to CoBB! 15 Bytes is a real achievement! Thanks to all entries, you guys did a great job.

I'm closing this thread now.

Greetings,
kv83

_________________
Image


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic This topic is locked, you cannot edit posts or make further replies.  [ 7 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB ® Forum Software © phpBB Group | DVGFX2 by: Matt