Acorn Arcade forums: Programming: Help! Faster Than Radix Sorting Algorithm in BASIC
| |
Help! Faster Than Radix Sorting Algorithm in BASIC |
| |
AdamP (03:59 6/10/2005)
SimonC (09:00 6/10/2005)
adamr (11:29 6/10/2005)
AdamP (11:31 6/10/2005)
not_ginger_matt (15:15 6/10/2005)
|
| |
|
Adam Speight |
Message #70209, posted by AdamP at 03:59, 6/10/2005 |
Member
Posts: 2
|
I have devised a sorting algorithm that promises to bo faster than radixsort, by upto 20%.
*** Scary Maths below ***
Radix Sort (Byte based)
O=8n
FTR Sort
O=sum( ((P[0]^2-P[0])/2) + ... +(P[p]^2-P[p])/2) ) + (n*Ceiling(Log((Log(8n)/Log2)-3))
where
P[] = Partition Array
Where each 8>=P[?]>=4
p = No. of Partition
n = number of items in list
o = number of items swapped/moved
For 64 items the equation equates to o=416.
*** End of scary maths ***
Implementation is broken somewhere but can't work out why?
Problems
---------
1. Lists with odd numbers of items, generates error.
2. Merges not merging correct
Def Sub Sort()
Orig[],Copy[],Parts[]
TheOrig=Orig
Break Orig[] into partitions
Where each 8>=PartSize(?)>=4
BubbleSort Each Partition 'No Laughing (Its key!)
repeat
repeat
Merge Partitions into copy
until all partitions merged into bigger partitions.
Swap MemoryAddress of Orig & Copy
until Merged into Single Partiton
If orig<>TheOrig then
Copy Orig[] into Copy[]
' Needed if copy[] clain from heap.
swap orig,copy
endif
display orig[]
end
BASIC Listing follows --{
MODE 12
ON ERROR REPORT RINT;" Error# ";ERR;" on line: ";ERL ND
PRINT"Experimental Sort"
INPUT"Number of items: ";N%
DIM Orig% 4*N%
DIM Copy% 4*N%
DIM Part%(N%)
TheOrig%=Orig%
REM PROCsetup
PartNo%=-1
REM {--
REM Randomise List
REM
PROCrandomiseList(Orig%)
PRINT
REM --}
REM {--
PRINT "Partition List {"
REM Partition List into chunks sized 8>=Partition()>=4
PROC_partition(N%)
PRINT';"Parts: ";PartNo%+1
PROC_print_List(Orig%)
PRINT "}"
REM {------------------------------
REM BubbleSort each Partion
REM
PRINT "Bubble Sorting Paritions {"
R%=0
FOR I%=0 TO PartNo%
PRINT'I%;" ";R%;"-";R%+Part%(I%)-1;
PRINT "[-]";
PROC_PrintPartOfList(Orig%,R%,R%+Part%(I%)-1)
PROC_BubbleSort( FN_Pos(Orig%,R%),Part%(I%)-1 )
R%=(R%+Part%(I%))
NEXT I%
PRINT "}"
REM --}
REM {-
PRINT "Mergeing List {"
REM Merge Partitions, until one remains
G%=1
REPEAT
R%=0
I%=0
REPEAT
PRINT I%,R%,N%,Part%(I%)
PROC_MergeLists(I%,Part%(R%),I%+Part%(R%),Part%(R%+G%))
Part%(I%)=Part%(I%)+Part%(R%)
I%+=Part%(R%)
R%=(2*G%)+R%
UNTIL R%>=PartNo%
SWAP Orig%,Copy%
PROC_print_List(Orig%)
G%=G%<<1
UNTIL Part%(0)=N%
PRINT"}"
IF Orig%<>TheOrig% THEN
PRINT" Copy Into Orig"
ENDIF
REM --}
REM {--
REM Display Sorted List
PROC_print_List(Orig%)
REM --}
END
DEF PROCrandomiseList(BaseAdr%)
PRINT'"[";
FOR I%=0 TO N%-1
PROC_put(Orig%,I%,RND(10))
PRINT;FN_get(Orig%,I%);",";
NEXT I%
PRINT;"]";
ENDPROC
:
DEF PROC_print_List(BaseAdr%)
PRINT;"[";
LOCAL I%
FOR I%=0 TO N%-1
PRINT;FN_get(BaseAdr%,I%);",";
NEXT I%
PRINT;"]"
ENDPROC
:
DEF PROCsetup
LOCAL I%
FOR I%=0 TO N%-1
PROC_put(Orig%,I%,10-I%)
NEXT
ENDPROC
:
DEF PROC_PrintPartOfList(BaseAdr%,StartAt%,Uptil%)
LOCAL I%
PRINT;"[";
I%=StartAt%
WHILE I%<=Uptil%
PRINT;FN_get(BaseAdr%,I%);",";
I%+=1
ENDWHILE
PRINT;"]"
ENDPROC
:
DEF PROC_partition(PartSize%)
LOCAL Part1%,Part2%
Part1%=PartSize%>>1
Part2%=Part1%
IF (Part1%<<1)<>PartSize% THEN
Part2%=Part2%+1
ENDIF
IF Part1%>8 THEN
PROC_partition(Part1%)
ELSE
PartNo%+=1
Part%(PartNo%)=Part1%
PRINT;Part1%;",";
ENDIF
IF Part2%>8 THEN
PROC_partition(Part2%)
ELSE
PartNo%+=1
Part%(PartNo%)=Part2%
PRINT;Part2%;",";
ENDIF
ENDPROC
=
DEF FN_Pos(BaseAdr%,Index%)
=BaseAdr%+(Index%<<2)
:
DEF PROC_BubbleSort(BaseAdr%,BubbleSize%)
LOCAL InL%, OutL%
FOR OutL%=0 TO (BubbleSize%-1)
FOR InL%=OutL%+1 TO (BubbleSize%-0)
IF !(BaseAdr%+(InL%<<2))<!(BaseAdr%+(OutL%<<2)) THEN
SWAP !(BaseAdr%+(OutL%<<2)),!(BaseAdr%+(InL%<<2))
REM PROC_print_List(Orig%)
ENDIF
NEXT InL%
NEXT OutL%
PRINT'"BS->";
PROC_print_List(Orig%)
ENDPROC
:
DEF PROC_put(BaseAdr%,Index%,Value%)
!(BaseAdr%+(Index%<<2))=Value%
ENDPROC
DEF FN_get(BaseAdr%,Index%)
=!(BaseAdr%+(Index%<<2))
DEF PROC_MergeLists( ListA%,LenA%, ListB%,LenB% )
LOCAL I%,J%,C%
I%=0
J%=0
C%=0
WHILE (I%<LenA%) AND (J%<LenB%)
IF FN_get(Orig%,ListA%+I%)<=FN_get(Orig%,ListB%+J%) THEN
PROC_put(Copy%,C%,FN_get(Orig%,ListA%+I%))
C%+=1:I%+=1
ELSE
PROC_put(Copy%,C%,FN_get(Orig%,ListB%+J%))
C%+=1:J%+=1
ENDIF
ENDWHILE
WHILE I%<LenA%
PROC_put(Copy%,C%,FN_get(Orig%,ListA%+I%))
C%+=1:I%+=1
ENDWHILE
WHILE J%<LenB%
PROC_put(Copy%,C%,FN_get(Orig%,ListB%+J%))
C%+=1:J%+=1
ENDWHILE
ENDPROC
} |
| |
 [ Log in to reply ] |
| |
|
Simon Challands |
Message #70210, posted by SimonC at 09:00, 6/10/2005, in reply to message #70209 |
 Right on, Commander!
Posts: 398
|
Don't know about the rest, but MODE 12 at the start? You still using an A310? |
| |
[ Log in to reply ] |
| |
|
Adam |
Message #70212, posted by adamr at 11:29, 6/10/2005, in reply to message #70209 |
Member
Posts: 112
|
Don't know - but a bit of indenting of the code would have helped the legibility a bit :-( |
| |
[ Log in to reply ] |
| |
|
Adam Speight |
Message #70213, posted by AdamP at 11:31, 6/10/2005, in reply to message #70212 |
Member
Posts: 2
|
I'm using Red Squirrel, and the Message box screwed up the indenting.
[Note from rich at 17:30, 6/10/2005. Use pre tags to preserve indenting. ] |
| |
[ Log in to reply ] |
| |
|
Richard Wilson |
Message #70216, posted by not_ginger_matt at 15:15, 6/10/2005, in reply to message #70209 |
Member
Posts: 63
|
I remember trying lots of different sorting algorithms on RISC OS a long time ago (for a 3d game) and found a radix sort doing 2 bits at a time (ie going from 4 buffers to a further 4 buffers) to be the fastest by quite a margin as it minimised effect of the poor memory bandwidth.
I've not got a RISC OS machine to hand right now to look at you code though I'm affraid :-(. |
| |
[ Log in to reply ] |
| |
|
Acorn Arcade forums: Programming: Help! Faster Than Radix Sorting Algorithm in BASIC |
