[Closed] Sort that array! (Winner: CoBB)

[kv83]

===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: Select all

.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.

[tr1p1ea]

Just to get things moving, note that this routine will change as its a simple bubble sort :

Code: Select all

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* .

[Jim e]

18 bytes... Mauhahahahaha PHEAR MY OPTIMISING SKILLZ

Code: Select all

;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...

[CoBB]

The power of swap'n'start sort!

Code: Select all

; 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

[Kozak]

The power of Gnome Sort. This is a preliminary version which hasn't been tested and is probably not complete.

[21 bytes]

Code: Select all

;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.

[sigma]

Code: Select all

/*
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

[kv83]

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