Acorn Arcade forums: Programming: (Long) ListArrays & Linear Sorts + Tree Sort
| |
(Long) ListArrays & Linear Sorts + Tree Sort |
| |
AdamPanic (13:58 29/5/2004)
ninj (14:57 4/6/2004)
|
| |
|
Adam Speight |
Message #55046, posted by AdamPanic at 13:58, 29/5/2004 |
Member
Posts: 6
|
How would it be possible to do the follow Data Structure in BASIC or any other languages.
DIM ListArray[ ]{}
Where every location is a list.
It usefullness is that it allow you create LINEAR SORTS
Let start with the simplist of all sorts.
Binary-Bin Sorting (O=32N)
==================
By Adam Speight
List[] = FN_BinBinSort( List[], 32 )
END
:
DEF FN_BinBinSort( InList[], Depth )
IF Depth<0 THEN =InList[]
LOCAL DIM ListArray[1]{}
LOCAL i,
FOR i=1 TO InList[].Items
b = ( InList[]{i} AND ( &1 << Depth ) >> Depth )
ListArray[b].AddItem InList[]{i}
NEXT i
IF ListArray[0].Items>1 THEN ListArray[]=FN_BinBinSort( ListArray[0], (Depth-1) )
IF ListArray[1].Items>1 THEN ListArray[]=FN_BinBinSort( ListArray[1], (Depth-1) )
=ListArray[0]+ListArray[1]
Maxmimum Recursion Depth: 32
Memory Requirements: 32 x ListArray[1]
Proof
-----
List[] = 11, 10, 01, 00
List[] = FN_BinBin( List[], 1 )
ListArray[0] = 01, 00
ListArray[1] = 11, 10
ListArray[0] = 00
ListArray[1] = 01
Returns: ListArray[0] = 00, 01
ListArray[0] = 10
ListArray[1] = 11
Returns: ListArray[1] = 10, 11
Returns: List[] = 00, 01, 10, 11
or
[11, 10, 01, 00]
[[01,00], [11,10]]
[[[00],[01]],[[10],[11]]]
Now lets take the ListArray into multiple dimensions
Sorting become more interesting and complicated.
First Implementation.
ArrayList Sorting (0=4N)
=================
By Adam Speight
List[] = FN_ArrayListSort( List[], 24 )
END
:
DEF FN_ArrayListSort( InList[], Depth )
IF Depth<0 Then =InList[]
LOCAL DIM ListArray[15,15]{}
LOCAL i,x,y
FOR i=1 TO InList[].Items
x=(InList[]{i} AND (&F0<<Depth)) >> Depth
y=(InList[]{i} AND ( &F<<Depth)) >> Depth
ListArray[x,y].AddItem InList[]{i}
NEXT i
InList[].Clear
FOR x=0 TO 15
FOR y=0 TO 15
IF ListArray[x,y].Items>1 THEN ListArray[x,y]=FN_ArrayListSort( ListArray[x,y], (Depth-8) )
InList[]+=ListArray[x,y]
NEXT y
NEXT x
=InList[]
Max. Recurision Depth: 4
Memory Requirements: 4 x ListArray[15,15]
Expanding the previous coding leads to the Second Implementation
Quayside Sorting (O=2N) (ie Containers in a port)
================
By Adam Speight
List[] = FN_QuaysideSort( List[], 16 )
END
:
DEF FN_QuaysideSort( InList[], Depth )
IF Depth<0 Then =InList[]
LOCAL DIM ListArray[255,255]{}
LOCAL i,x,y
FOR i=1 TO InList[].Items
x=(InList[]{i} AND (&FF00<<Depth)) >> Depth
y=(InList[]{i} AND ( &FF<<Depth)) >> Depth
ListArray[x,y].AddItem InList[]{i}
NEXT i
InList[].Clear
FOR x=0 TO 255
FOR y=0 TO 255
IF ListArray[x,y].Items>1 THEN ListArray[x,y]=FN_QuaysideSort( ListArray[x,y], (Depth-16) )
InList[]+=ListArray[x,y]
NEXT y
NEXT x
=InList[]
Max. Recurison Depth: 2
Memory Requirements: 2 x ListArray[255,255]
Now if you had at least 16GB of Memory,
Warp Sorting (N)
============
By Adam Speight
List[] = FN_WarpSort( List[] )
END
:
DEF FN_WarSort( InList[] )
LOCAL DIM ListArray[255,255,255,255]
LOCAL i,x,y,z,t
FOR i=1 TO InList[].Items
x=(InList[]{i} AND (&FF<<24)) >> 24
y=(InList[]{i} AND (&FF<<16)) >> 16
z=(InList[]{i} AND (&FF<<08)) >> 8
t=(InList[]{i} AND (&FF<<00)) >> 00
ListArray[x,y,z,t].AddItem InList[]{i}
NEXT i
InList[].Clear
FOR x=0 TO 255
FOR y=0 TO 255
FOR z=0 TO 255
FOR t=0 TO 255
InList[]+=ListArray[x,y,z,t]
NEXT t
NEXT z
NEXT y
NEXT x
=InList[]
Max. Recurision Depth: 0
Warp Sorting could be converted into a Counting Sort, which I call MatrixCountSort
MatrixCountSort (0=N)
===============
By Adam Speight
List[] = FN_MatrixCountSort( List[] )
LOCAL DIM C%(255,255,255,255)
LOCAL i,x,y,z,t,r
FOR i=1 TO InList[].Items
x=(InList[]{i} AND (&FF<<24)) >> 24
y=(InList[]{i} AND (&FF<<16)) >> 16
z=(InList[]{i} AND (&FF<<08)) >> 8
t=(InList[]{i} AND (&FF<<00)) >> 00
C%[x,y,z,t]+=1
NEXT i
InList[].Clear
i=0
FOR x=0 TO 255
FOR y=0 TO 255
FOR z=0 TO 255
FOR t=0 TO 255
IF C%(x,y,z,y)>0 Then
FOR r=1 TO 1
InList[]{r)= (x<<24) + (x<<16) + (x<<8) + (x<<0)
NEXT r
NEXT t
NEXT z
NEXT y
NEXT x
=InList[]
If the ArrayList[]{} also had the following properties.
ArrayList[x,].RowEmpty
ArrayList[,y].ColEmpty
You can speed up the routines.
Quayside Sorting (Ver. 2.00)
================
By Adam Speight
List[] = FN_QuaysideSort2( List[], 16 )
END
:
DEF FN_QuaysideSort2( InList[], Depth )
IF Depth<0 Then =InList[]
LOCAL DIM ListArray[255,255]{}
LOCAL i,x,y
FOR i=1 TO InList[].Items
x=(InList[]{i} AND (&FF00<<Depth)) >> Depth
y=(InList[]{i} AND ( &FF<<Depth)) >> Depth
ListArray[x,y].AddItem InList[]{i}
NEXT i
InList[].Clear
FOR x=0 TO 255
IF NOT(ArrayList(x,).RowEmpty) THEN
FOR y=0 TO 255
IF ListArray[x,y].Items>1 THEN ListArray[x,y]=FN_QuaysideSort2( ListArray[x,y], (Depth-16) )
InList[]+=ListArray[x,y]
NEXT y
ENDIF
NEXT x
=InList[]
Whilst I'm writing about sorting list an implementation of a TreeSort in BASIC.
TreeSort
========
By Adam Speight
MODE 15
DIM List(10000)
DIM Tree(10000,3)
Lower=0:Upper=10000
REPEAT
n=RND(998)+2
FOR i=1 TO n
List(i)=INT(RND(ABS(Lower-Upper)))+Lower
NEXT i
CLS
T=TIME
PRINT"List Size: "+STR$(n)+" Items"
PRINT "Unordered"
PROClist
PROC_TreeSort
PRINT "Sorted"
PROClist
PRINT (TIME-T)/100;" Seconds"
PRINT
REM PROCtree
PRINT;'"Press 'A' Key To Repeat"
REPEAT
K$=CHR$(INKEY 100 )
UNTIL K$="A"
UNTIL FALSE
END
:
DEF PROClist
PRINT"[ ";:FOR i=1 TO n:PRINT;List(i);", ";:NEXT i::PRINT;"]"
ENDPROC
:
DEF PROCtree
PRINT:PRINT;"Node","Value","<",">","*":FOR g=1 TO Max:
PRINT;g;,;Tree(g,0);,;Tree(g,1);,;Tree(g,2);,;Tree(g,3):NEXT g
ENDPROC
:
DEF PROC_TreeSort
REM - Partially Build Tree
FOR i=1 TO n
Tree(i,0)=0: Tree(i,1)=0: Tree(i,2)=0: Tree(1,3)=0
NEXT i
Tree(1,0)=List(1): Tree(1,3)=1: Max=1
FOR i=2 TO n
REM PROCtree
PROC_Branch(i,1)
NEXT i
i=0
PROC_Rebuild(1)
ENDPROC
:
DEF PROC_Branch(l,s)
IF List(l)=Tree(s,0) THEN Tree(s,3)+=1
IF (List(l)<Tree(s,0)) AND (Tree(s,1)>0) THEN PROC_Branch(l,Tree(s,1))
IF (List(l)<Tree(s,0)) AND (Tree(s,1)=0) THEN
Max+=1: Tree(s,1)=Max: Tree(Max,0)=List(l): Tree(Max,3)=1
ENDIF
IF (List(l)>Tree(s,0)) AND (Tree(s,2)> 0) THEN PROC_Branch(l,Tree(s,2))
IF (List(l)>Tree(s,0)) AND (Tree(s,2)= 0) THEN
Max+=1: Tree(s,2)=Max: Tree(Max,0)=List(l): Tree(Max,3)=1
ENDIF
ENDIF
ENDPROC
:
DEF PROC_Rebuild(n)
IF Tree(n,1)>0 THEN PROC_Rebuild(Tree(n,1))
FOR j=1 TO Tree(n,3):
i+=1: List(i)=Tree(n,0)
NEXT j
IF Tree(n,2)>0 THEN PROC_Rebuild(Tree(n,2))
ENDPROC
Note:
The Data in the Tree() array can mathematically prove if a list is sorted and in which direction.
Ascendig Order
--------------
SUM( Tree(1 ,1) ... Tree( n,1) ) = 0
--
\ Tree(1 ,1) ... Tree( n,1) = 0
/
--
Desecending
-----------
SUM( Tree(1,2) ... Tree (n,2) ) = 0
--
\ Tree (1,2) ... Tree ( n,2) = 0
/
--
-- Adam Speight |
| |
 [ Log in to reply ] |
| |
|
ninjah |
Message #55389, posted by ninj at 14:57, 4/6/2004, in reply to message #55046 |
Member
Posts: 288
|
My BASIC is too rusty - but if you're just asking for nested lists, you can do this in any proper programming language. In BASIC you'd have to resort to pointers (i.e. DIMming your own chunk of memory and doing it word by word).
In Perl you could do it by having a list of numbers, some of which may be references to other lists. You could even have straight lists inside other lists, but I don't personally like the syntax.
You could write:
@list = (1, 5, [4, 8, 2], 4, [12, [9]])
Then ref($list[1]) = false and $list[1] = 5
And ref($list[2]) = true and @{$list[2]} = (4, 8, 2)
Also, $list[2]->[1] = 8
You can do exactly the same in Python, probably more elegantly, though I'm not as familiar with the syntax at the moment. And of course you can also do it in C, C++, Java, Haskell and any other proper language. |
| |
[ Log in to reply ] |
| |
|
Acorn Arcade forums: Programming: (Long) ListArrays & Linear Sorts + Tree Sort |
