Mergesort of a linked list/Forum (SoCoder)

Forum Home

Cobra

Mergesort of a linked list

User

Message

Posted : Tuesday, 25 August 2009, 08:47 | Permalink | Mark Here

HoboBen

WW Entries : 9

Edit: solved

I'm trying to implement Mergesort as it seems to be a good choice for sorting a linked list.

I have a working bubblesort implementation, but it's far too slow for a list this size.

My code is crashing though - can anyone perhaps see where I went wrong? I think it's either crashing during the OrderTiles_MergeSort_merge procedure, or just after it.

Thanks

My tile type definition:

Type tiles = Record

    x, y: Integer   

    // Other parameters omitted for this example
    
EndType ; export

-->

The code:

// I call OrderTiles_MergeSort_sort(tileList)

Procedure OrderTiles_MergeSort_sort(ByRef tileList: List of tiles)
Var
    tile1: ^tiles
    tile2: ^tiles
    
    tileLast: ^tiles
    tileFirst: ^tiles
    
    tResult : List of tiles
    tLeft : List of tiles
    tRight: List of tiles
    
    i, count, middle: Integer
Begin

    count = CountList(tileList)
    If count <= 1 then exit
    //PutLog("Count: "+count)
    middle = (count / 2) - 1 

    Loop tile1 through tileList
        
        If i <= middle then
            tile2 = NewItem(tLeft)
            CloneTile(tile1, tile2)
        Else
            tile2 = NewItem(tRight)
            CloneTile(tile1, tile2)
        Endif
        
        Inc(i)    
    EndLoop
    
    OrderTiles_MergeSort_sort(tLeft)
    OrderTiles_MergeSort_sort(tRight)
    
    tileLast = LastItem(tLeft)
    tileFirst = FirstItem(tRight)
    
    If tileLast.x > tileFirst.x
         PutLog("Merge...")
         OrderTiles_MergeSort_merge(tResult, tLeft, tRight)
    Else
         Loop tile1 through tLeft
            tile2 = NewItem(tResult)
            CloneTile(tile1, tile2)
            Free(tile1)
         EndLoop
         Loop tile1 through tRight
            tile2 = NewItem(tResult)
            CloneTile(tile1, tile2)
            Free(tile1)
         EndLoop
    Endif    
    
    // return result
    Loop tile1 through tileList
        Free(tile1)
    EndLoop
    
    Loop tile1 through tResult
        tile2 = NewItem(tileList)
        CloneTile(tile1, tile2)
        Free(tile1)
    EndLoop

End

Procedure OrderTiles_MergeSort_merge(ByRef tResult: List of tiles, ByRef tLeft: List of tiles, ByRef tRight: List of tiles)
Var
    tile1, tile2 : ^tiles
    tileFirst1 : ^tiles
    tileFirst2 : ^tiles
Begin

    While ( (CountList(tLeft) > 0) and (CountList(tRight) > 0) )

        tileFirst1 = FirstItem(tLeft)
        tileFirst2 = FirstItem(tRight)
            
        If tileFirst1.x <= tileFirst2.x
            tile1 = FirstItem(tResult)
            CloneTile(tileFirst1, tile1)
            Free(tile1)
        Else
            tile1 = FirstItem(tResult)
            CloneTile(tileFirst2, tile1)
            Free(tile1)
        Endif
    Wend
    
    If (CountList(tLeft) > 0) 
         Loop tile1 through tLeft
            tile2 = NewItem(tResult)
            CloneTile(tile1, tile2)
            Free(tile1)
         EndLoop
    Else  
         Loop tile1 through tRight
            tile2 = NewItem(tResult)
            CloneTile(tile1, tile2)
            Free(tile1)
         EndLoop
    Endif
    
End

Procedure CloneTile(tile1: ^tiles, tile2: ^tiles)
Var

    x, y: Integer   

    tileClass: ^terrainTileClasses
    tileTexture: ^terrainTileTextures
    
    mask: Integer = 0
      
Begin

    { Tile 2 }
    tile2.x = tile1.x
    tile2.y = tile1.y
    tile2.tileClass = tile1.tileClass
    tile2.tileTexture = tile1.tileTexture
    tile2.mask = tile1.mask

End

-->

-----

github

Posted : Tuesday, 25 August 2009, 08:58 | Permalink | Mark Here

HoboBen

WW Entries : 9

Whoops, spoke too soon.... I always end up solving it seconds after I post in the forum.

Fixed merge function:


Procedure OrderTiles_MergeSort_merge(ByRef tResult: List of tiles, ByRef tLeft: List of tiles, ByRef tRight: List of tiles)
Var
    tile1, tile2 : ^tiles
    tileFirst1 : ^tiles
    tileFirst2 : ^tiles
Begin

    While ( (CountList(tLeft) > 0) and (CountList(tRight) > 0) )

        tileFirst1 = FirstItem(tLeft)
        tileFirst2 = FirstItem(tRight)
            
        If tileFirst1.x <= tileFirst2.x
            tile1 = NewItem(tResult)
            CloneTile(tileFirst1, tile1)
            Free(tileFirst1)
        Else
            tile1 = NewItem(tResult)
            CloneTile(tileFirst2, tile1)
            Free(tileFirst2)
        Endif
    Wend
    
    If (CountList(tLeft) > 0) 
         Loop tile1 through tLeft
            tile2 = NewItem(tResult)
            CloneTile(tile1, tile2)
            Free(tile1)
         EndLoop
    Else  
         Loop tile1 through tRight
            tile2 = NewItem(tResult)
            CloneTile(tile1, tile2)
            Free(tile1)
         EndLoop
    Endif
    
End

-->

And it's really, really, really fast!

It takes almost no time at all, compared to minutes or hours with bubblesort.

I'm so excited to have solved it. Cool!!!!!!

-----

github

Posted : Wednesday, 26 August 2009, 10:26 | Permalink | Mark Here

Phoenix

WW Entries : 5

Smells like a proper candidate for the code snippets section, wink wink