Acorn Arcade forums: Programming: Linear Sort in BASIC
| |
Linear Sort in BASIC |
| |
AdamPanic (09:36 22/6/2004)
AdamPanic (16:27 23/6/2004)
ninj (16:35 23/6/2004)
AdamPanic (11:45 26/6/2004)
AdamPanic (15:45 20/8/2004)
AdamPanic (01:42 13/7/2004)
|
| |
|
Adam Speight |
Message #55956, posted by AdamPanic at 09:36, 22/6/2004 |
Member
Posts: 6
|
The following progam demostrates ho to perform a linear sort in BASIC. The methods is a variant of the Binary-Bin featured in the ListArray topic, I've taken out the recursion and added code to sort out the negative numbers.
Radix Sort
----------
By Adam Speight
MODE 0
ON ERROR REPORT:PRINT ERR;" on line: ";ERL:END
Max%=1000
DIM List%(Max%+2)
DIM R%(1,Max%+2)
Lower%=-64566:Upper%=(2^30)-1
REPEAT
n%=RND(Max%)+2
FOR i%=1 TO n%
List%(i%)=INT(RND(ABS(Lower%-Upper%)))+Lower%
NEXT i%
CLS
PRINT "Unordered"
PROClist
T%=TIME
PROC_RadixSort
T%=TIME-T%
PRINT' "Sorted"
PROClist
PRINT
PRINT;n%;" items in ";(T%/100);" Sec."
PRINT
PRINT;'"Press 'A' Key To Repeat"
REPEAT
K$=CHR$(INKEY 10 )
UNTIL K$="A"
UNTIL FALSE
END
:
DEF PROClist
PRINT"[ ";
FOR i%=1 TO n%
PRINT;List%(i%);", ";
NEXT i%
PRINT;"]"
ENDPROC
:
DEF PROC_RadixSort
LOCAL d%,i%,b%,j%,m%,k%
PRINT;"Radix Sort ( ";n%;" Items)"
REM -- Find Highest Value --
m%=0
FOR i%=1 TO n%
IF List%(i%)>m% THEN
m%=ABS(List%(i%))
ENDIF
NEXT i%
PRINT;"Highest: ";m%
REM -- Workout m% Log 2 --
b%=1
k%=
WHILE b%<m%
k%+=1:
b%=b%*2
ENDWHILE
PRINT;m%;"<=2^";k%
m%=k%
REM -- Radiix Sorting --
FOR d%=0 TO m% STEP 1
PRINT;d%;" ";
REM PROClist
R%(0,0)=0
R%(1,0)=0
FOR i%=1 TO n%
b%=(List%(i%) AND (%1<<d%) ) >> d%: REM Get bit state
R%(b%,0)+=1
R%(b%,R%(b%,0))=List%(i%)
NEXT i%
REM -- Recombine Lists --+
i%=0
IF R%(0,0)>0 THEN
FOR j%=1 TO R%(0,0)
i%+=1
List%(i%)=R%(0,j%)
NEXT j%
ENDIF
IF R%(1,0)>0 THEN
FOR j%=1 TO R%(1,0)
i%+=1
List%(i%)=R%(1,j%)
NEXT j%
ENDIF
NEXT d%
REM { Split Positve & Negative Values }
PRINT;"-"
PROClist
R%(0,0)=0
R%(1,0)=0
FOR i%=1 TO n%
IF List%(i%)<0 THEN
REM -- Negative Values List --
R%(0,0)+=1
R%(0,R%(0,0))=List%(i%)
ELSE
REM -- Positve Values List --
R%(1,0)+=1
R%(1,R%(1,0))=List%(i%)
ENDIF
NEXT i%
REM { Rebuild }
i%=0
IF R%(0,0)>0 THEN
FOR j%=1 TO R%(0,0)
i%+=1
List%(i%)=R%(0,j%)
NEXT j%
ENDIF
IF R%(1,0)>0 THEN
FOR j%=1 TO R%(1,0)
i%+=1
List%(i%)=R%(1,j%)
NEXT j%
ENDIF
ENDPROC |
| |
 [ Log in to reply ] |
| |
|
Adam Speight |
Message #56089, posted by AdamPanic at 16:27, 23/6/2004, in reply to message #55956 |
Member
Posts: 6
|
This is an improvement of the above program. It is called Half-Radix because it requires only half the memory, storing only the radix with a set value.
A further improvement would be to claim the memory from a stack and then release it afterwards.
Half-Radix Sort
---------------
By Adam Speight
MODE 0
ON ERROR REPORT:PRINT ERR;" on line: ";ERL:END
Max%=25000
DIM List%(Max%+2)
DIM R%(Max%+2)
Lower%=-65336
Upper%=64556
REPEAT
n%=RND(Max%)+2
FOR i%=1 TO n%
List%(i%)=INT(RND(ABS(Lower%-Upper%)))+Lower%
NEXT i%
CLS
PRINT "Unordered"
PROClist
T%=TIME
PROC_Half-RadixSort
T%=TIME-T%
PRINT' "Sorted"
PROClist
PRINT
PRINT;n%;" items in ";(T%/100);" Sec."
PRINT
PRINT;'"Press 'A' Key To Repeat"
REPEAT
K$=CHR$(INKEY 10 )
UNTIL K$="A"
UNTIL FALSE
END
:
DEF PROClist
PRINT"[ ";
FOR i%=1 TO n%
PRINT;List%(i%);", ";
NEXT i%
PRINT;"]"
ENDPROC
:
DEF PROC_Half-RadixSort
LOCAL d%,i%,b%,j%,m%,k%,e%,f%
PRINT;"Half-Radix Sort ( ";n%;" Items)"
REM -- Find Highest Value --
m%=0
FOR i%=1 TO n%
IF List%(i%)>m% THEN
m%=ABS(List%(i%))
ENDIF
NEXT i%
PRINT;"Highest: ";m%
b%=1
k%=0
WHILE b%<m%
k%+=1
b%=b%*2
ENDWHILE
PRINT;m%;"<=2^";k%
m%=k%
m%=31
FOR d%=0 TO m% STEP 1
PRINT;d%;" ";
REM PROClist
R%(0)=0
e%=0
FOR i%=1 TO n%
b%=(List%(i%) AND (%1<<d%) ) >> d%
IF b%=1 THEN
REM -- Full --
R%(0)+=1
R%(R%(0))=List%(i%)
ELSE
REM -- Empties --
e%+=1
List%(e%)=List%(i%)
ENDIF
NEXT i%
i%=e%
IF R%(0)>0 THEN
FOR j%=1 TO R%(0)
i%+=1
List%(i%)=R%(j%)
NEXT j%
ENDIF
NEXT d%
PRINT;"-"
REM -- Float Positives to top --
e%=0
R%(0)=0
FOR i%=1 TO n%
IF List%(i%)>=0 THEN
R%(0)+=1
R%(R%(0))=List%(i%)
ELSE
e%+=1
List%(e%)=List%(i%)
ENDIF
NEXT i%
i%=e%
IF R%(0)>0 THEN
FOR j%=1 TO R%(0)
i%+=1
List%(i%)=R%(j%)
NEXT j%
ENDIF
ENDPROC |
| |
[ Log in to reply ] |
| |
|
ninjah |
Message #56090, posted by ninj at 16:35, 23/6/2004, in reply to message #56089 |
Member
Posts: 288
|
Jolly good. How do these algorithms compare to quicksort? |
| |
[ Log in to reply ] |
| |
|
Adam Speight |
Message #56264, posted by AdamPanic at 11:45, 26/6/2004, in reply to message #56090 |
Member
Posts: 6
|
Jolly good. How do these algorithms compare to quicksort?
Quick Sort
Worst case: n*n
Hard-Radix Sort
+ & - Case: All cases: (32+2)n
+ Only: n(m Log 2)
where m=Highest value in dataset.
In theory Half-Radix should be faster, but in practice it is slower because it swaps more elements.
This may be to do with the test being perform in software emulation of hardward (Red Squirrel), it would be better to check again in native hardware.
Yet it does have a advantage over Quicksort which is the radix-bit checking can be parallalised given the right hardware. |
| |
[ Log in to reply ] |
| |
|
Adam Speight |
Message #56899, posted by AdamPanic at 01:42, 13/7/2004, in reply to message #55956 |
Member
Posts: 6
|
Whoops! That should be a Logical Shift Right not an Arithmitic Shift Right
The following line in each of the aboove programs need to be changed from:
b%=(List%(i%) AND (%1<<d%) ) >> d%: REM Get bit state
to
b%=(List%(i%) AND (%1<<d%) ) >>> d%: REM Get bit state. |
| |
[ Log in to reply ] |
| |
|
Adam Speight |
Message #57365, posted by AdamPanic at 15:45, 20/8/2004, in reply to message #56089 |
Member
Posts: 6
|
Arm CodeVersion
; ** Half-Radix Sort **
MOV R,#1
.radix MOV E,#0
MOV F,#0
MOV I,#0
.loop1 ADD I,I,#1
LDR D,[ListBase,I,ASL#2]
BIC R,D
BEQ bit1 ;bit = 1
ADD E,E,#1
STR D,[TempBase,E,ASL#2]
B skip1
.bit1 ADD F,F,#1
STR D,[Temp,Base,F,ASL#2]
.skip1 CMP I,N
BLT loop1
; Add Fulls to back of list
CMP F,#0
BEQ skip2
MOV I,#0
.loop2 ADD I,I,#1
ADD E,E,#1
LDR D,[TempBase,I,ASL#2]
STM D,[ListBase,E,ASL#2]
CMP I,F
BLT loop2
.skip2 MOVS R,R,LSL#1
BCC radix ; While Radix<>0
; MOV E,#0
MOV F,#0
MOV I,#0
.loop3 ADD I,I,#1
LDRS D,[ListBase,I,ASL#2]
BEQ skip3
ADD E,E,#1
STR D,[ListBase,E,ASL#2]
B skip4
.skip3 ADD F,F,#1
LDR D,[Te
mpBase,F,ASL#2]
.skip4 CMP I,N
BLT loop3
CMP F,#0
BEQ skip5
. MOV I#0
.loop4 ADD I,I,#1
ADD E,E,#1
LDR D,[TempBase,I,ASL#2]
STM D,[ListBase,E,ASL#2]
CMP I,F
BL loop4
.skip 5 MOV PC,R14 |
| |
[ Log in to reply ] |
| |
|
Acorn Arcade forums: Programming: Linear Sort in BASIC |
