Who wrote SortList()?

Because I checked the function source and it appears to use a BUBBLE SORT, the slowest sorting algorithm on the face of the planet!

You should use this instead. It's Mergesort for linked lists:
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

BubbleSort has a worst case time of O(N^2) and is stable.
Merge sort has a worst case time of O(n log n) and is also stable.
(Stable means two elements with the same value will retain their relative locations in the list.)

Merge sort for linked lists also does not require more than a few extra variables of storage to perform the sort. So it is memory efficient.

See this page for speed comparisons between sorting algorithms:
http://linux.wku.edu/~lamonml/algor/sort/sort.html

Look at how fast Mergesort is there compared to Bubble sort. Bubble takes at least several seconds to sort 1000 objects, whereas Merge sort can sort over 100,000 objects in that same time frame.

Quicksort is the fastest, but much more complicated, and recursive, and performs really slowly on lists that are nearly sorted. I don't see any mention anywhere about Mergesort having those same issues.

[edit]

Aha, busted!

ModuleInfo "Author: Mark Sibly"

[/edit]

BubbleSort has one good thing: Its runtime is not a constant no mather of the dataset (as QuickSort has it for example). It can go down to O(N) on a presorted dataset, while QuickSort will still have to run on its O(n lb(n)) (lb for log binary)

In a game environment I think especially this special thing is a very great thing as (at least I) enter my data once to a dataset and don't rearrange it anymore afterwards. I only add or remove new thing so it will still run on O(N) with once an O(N^2), while QuickSort would always be O(N lb(N)) which results in quite some time lost just because of its incapability of recognizing presorted data.

Actually, sswift, I tried adding mergesort (same page as the one you found) to the linked list, and unfortunately it seems to result in decreased speed (by about 600%).

I am most likely doing something wrong (I'd bet on it if it wasn't such a stupid bet), so here's the code if anyone wants to take a look at it.

    Method Sort( ascending=True )
         Local h:TLink = FirstLink( )
         If h = Null Then Return
         If h.NextLink( ) = Null Then Return ' No need to sort one element
         h = ISort( h, _head )
         _head._succ = h
         While h.NextLink( )
             h = h.NextLink( )
         Wend
         If Not ascending Then Swap Reversed( )
     End Method
     
     ' Internal sort function
     Function ISort:TLink( h:TLink, oh:TLink )
         Local p:TLink, q:TLink, e:TLink, tail:TLink, oldhead:TLink
         Local insize%, merges%, psize%, qsize%, i%
         If h = Null Then Return
         insize = 1
         While True
             p = h
             oldhead = h
             h = Null
             tail = Null
             merges = 0
             While p
                 merges :+ 1
                 q = p
                 psize = 0
                 For i = 0 To insize-1
                    psize :+ 1
                    q = q.NextLink( )
                    If Not q Then Exit
                 Next
                 
                 qsize = insize
                 
                 While psize > 0 Or ( qsize > 0 And q )
                     If psize = 0 Then
                        e = q
                        q = q.NextLink( )
                        qsize :- 1
                     ElseIf qsize = 0 Or Not q
                        e = p
                        p = p.NextLink( )
                        psize :- 1
                     Else
                        Local cmp%
                        If p._value And q._value Then
                             cmp = p._value.Compare( q._value )
                         ElseIf p._value
                             cmp = -1
                         ElseIf q._value
                             cmp = 1
                         Else
                             cmp = 0
                         EndIf
                         
                         If cmp <= 0 Then
                             e = p
                             p = p.NextLink( )
                             psize :- 1
                         Else
                             e = q
                             q = q.NextLink( )
                             qsize :- 1
                         EndIf
                     EndIf
                     
                     If tail Then
                         tail._succ = e
                     Else
                         h = e
                     EndIf
                     
                     tail = e
                     
                 Wend
                 
                 p = q
             Wend
             tail._succ = oh
             h._pred = oh
             If merges <= 1 Then Return h
             insize :* 2
         Wend
     End Function

At the moment, I don't have time to go over it and ensure it's working 100% correctly.

sswift - not exactly related, but..

If you have a poke around in BlitzMax internals you will find a thing called TMaps:
C:\Program Files\BlitzMax\mod\brl.mod\map.mod\map.bmx

It is very useful for mapping names to Strings/Objects. Items are automatically sorted into a binary tree for fast access. In the example below you will notice that the EachIn loop retrieves the entries already sorted.

Very simple example:

sites:TMap = New TMap

sites.Insert("pf","www.playerfactory.co.uk")
sites.Insert("cw","www.codersworkshop.com")
sites.Insert("bb","www.blitzbasic.com")
sites.Insert("goo","www.google.com")

Print String(sites.ValueForKey("bb"))
Print "==============="

For mysite:TNode = EachIn sites
	Print String(mysite.Key())+"  "+String(mysite.Value())
Next

And, if you would like a hash table:

Rem
    HASHTABLE OBJECT
    
    - M.Laurenson/Defoc8 2006
EndRem

Rem
    Defoc would appreciate if you credited him if you
    used this.  No credit is to go to me.
    
    -Noel
EndRem

Strict

Import Brl.Blitz
Import Brl.LinkedList
Import "hash.c"

Extern "C"
    Function __c_hash:Int(key$z, length:Int, initval:Int)="Hash"
EndExtern

Global HashKey:Int(name:String) = gHashKey

Function gHashKey%( name:String )
    Return __c_hash( name, name.Length, 0 )
End Function

Type gHashTable
    'private:

    Field table:TList[]
    
    'protected:
    
    Method _rement(key:Int)
        For Local entry:gHashEntry = EachIn table[key Shr 24]
            If entry.key = key
                entry.node.Remove( )
                Return
            EndIf
        Next
    End Method
    
    Method _addent(key:Int,n:String,o:Object)
        Local entry:gHashEntry = New gHashEntry
        entry.key = key
        entry.obj = o 
        entry.name = n
        entry.node = table[key Shr 24].AddLast(entry)
    End Method
    
    Method _getent:Object(key:Int)
        For Local entry:gHashEntry = EachIn table[key Shr 24]
            If entry.key = key
                Return entry.obj
            EndIf
        Next
        Return Null
    End Method
    
    'public:
    
    Method New()
        table=New TList[256]
        For Local n:Int = 0 To 255
            table[n] = New TList
        Next
    End Method
    
    Method SetEntry( name:String, obj:Object )
        Local key:Int = HashKey( name )
        Local o:Object = _getent(key)
        If o And o <> obj Then _rement(key)
        _addent(key,name,obj)
    End Method
    
    Method InsertEntry(name:String,obj:Object)
        Local key:Int = HashKey( name )
        _addent(key,name,obj)
    End Method
    
    Method RemoveEntry(name:String)
        Local key:Int = HashKey( name )
        _rement(key)
    End Method
    
    Method GetEntry:Object(name:String)
        Local key:Int = HashKey( name )
        Return _getent(key)
    End Method
    
    Method Flush()
        For Local n:Int = 0 To 255
            table[n].Clear( )
        Next
    End Method 
    
    Method GetEntryCount(index:Int)
        Return table[index].Count( )
    End Method
    
    Method ToArray:Object[]( iters%=0 )
        Local amnt%=0
        For Local i:Int = 0 To 255
            amnt :+ table[i].Count( )
        Next
        Local obj:Object[amnt]
        Local c%=0
        For Local i:Int = 0 To 255
            For Local n:gHashEntry = EachIn table[i]
                If iters > 0 Then
                obj[c] = n
                Else
                obj[c] = n.obj
                EndIf
                c:+1
            Next
        Next
        Debuglog " table size: "+c
        Return obj
    End Method
    
    Method ObjectEnumerator:gHashTableEnum( )
        Local e:gHashTableEnum = New gHashTableEnum
        e.arr = ToArray( )
        Return e
    End Method
End Type

Type gHashTableEnum
    Field idx%=0
    Field arr:Object[]
    
    Method HasNext%( )
        If idx < arr.Length Then Return True
        Debuglog "Has no more elements in the enumerator at idx "+idx
        Debuglog "Array length is "+arr.Length
        Return False
    End Method
    
    Method NextObject:Object( )
        Debuglog " idx: "+idx
        idx :+ 1
        Return arr[idx-1]
    End Method
End Type

Type gHashEntry
    Field key:Int
    Field name:String
    Field obj:Object
    Field node:TLink
End Type

Mapping names? Not related?

Poking around in it, it seems very related!

From what I can tell, I'm pretty sure that you could do this:

sites.Insert(Order, ThisSprite)

Then each time you add a sprite to it, it would recurse down the binary tree, and insert the sprite at the correct location.

And as in your example above, using EachIn to loop through them would return them in the desired order.

If you then wanted to change the order of one, you would simply remove it from the list, and then reinsert it with the new Order.


This could prove most useful! But is it supported? And is it in the docs anywhere?

Do I just have to guess at what the methods do? :-)


I wonder if it is faster to use a binary tree rather than looping through a list and simply inserting the sprite at the right location? My intutution says "likely", but I'm not sure. I guess if you end up with a balanced tree, the answer is yes, but if you insert everything in the correct order in the first place you might end up with a string instead of a tree.

Unfortunately, I'm not very knowledgeable when it comes to binary trees. I know the basics, but I'd have to go research them to figure out how stepping down a tree and inserting values to the left or right branch if they are greater or less than the current node, leads to a list which is sorted.

Are you SURE that that thing always sorts the strings correctly?

You know reading all marks code, and noel's code... I'm not really sure this OOP stuff actually makes code easier to understand. :-)

I've found that a good sort for a linked list type structure is the selection sort. The idea is to run through the list and find the smallest or largest element, reduce the size of the unsorted list by 1 and repeat.

It always does N swaps and (N^2)/2 comparisons. It's simple to implement so there's no overhead or recursion or function calls.

LOL i have allso used merge sort from the same page ;)

heres my result, its just a little faster then your version noel :/ it must be the overhead of using a double linked list.

some timings of sorting 100000 integers in a type:
mine = 0.199000001
noels = 0.257999986
array = 0.0869999975
array of ints = 0.0120000001

Function MergeSortList( slist:TList)
	Local p:TLink, q:TLink, e:TLink, tail:TLink, oldhead:TLink
	Local insize:Int, nmerges:Int, psize:Int, qsize:Int, i:Int
	Local list:TLink
	
	If slist = Null Then Return
	If slist._head._succ <> slist._head Then list = slist._head._succ
	If list = Null Then Return
	
	insize = 1
	
	Repeat
		p = list
		oldhead = list
		list = Null
		tail = Null
		
		nmerges = 0
		
		While p <> Null
			nmerges :+ 1
			q = p
			psize = 0
			For i = 0 Until insize
				psize :+ 1
				If q._succ = oldhead Then
					q = Null
				Else
					q = q._succ
				EndIf
				If q = Null Then Exit
			Next
			
			qsize = insize
			While (psize > 0) Or ((qsize > 0) And (q <> Null))
				If psize = 0 Then
					e = q
					q = q._succ
					qsize :- 1
					If q = oldhead Then q = Null
				ElseIf (qsize = 0) Or (q = Null) Then
					e = p
					p = p._succ
					psize :- 1
					If p = oldhead Then p = Null
				ElseIf p._value.Compare( q._value) <= 0 Then
					e = p
					p = p._succ
					psize :- 1
					If p = oldhead Then p = Null
				Else
					e = q
					q = q._succ
					qsize :- 1
					If q = oldhead Then q = Null
				EndIf
								
				If tail <> Null Then
					tail._succ = e
				Else
					list = e
				EndIf
				e._pred = tail				
				tail = e					
			Wend
			p = q
		Wend
		tail._succ = list
		list._pred = tail
		If nmerges <= 1 Then Return
		insize :* 2
	Forever	
EndFunction