Mergesort of a linked list

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|32\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Cobra -> Mergesort of a linked list
Tue, 25 Aug 2009, 09:47
HoboBen	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 --v 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 --v -=-=- blog \| work \| code \| more code
Tue, 25 Aug 2009, 09:58
HoboBen	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 --v 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!!!!!! -=-=- blog \| work \| code \| more code
Wed, 26 Aug 2009, 11:26
Phoenix	Smells like a proper candidate for the code snippets section, wink wink