Mergesort a linked list

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|454\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> Variables

HoboBen	Created : 26 August 2009 Edited : 26 August 2009 Language : Cobra Mergesort a linked list
Mergesort is a sorting algorithm that is especially suited to sorting linked lists. Note: You really, really don't want to sort any lists that contain strings!!! Feel free to use for any purpose, with or without attribution. { Mergesort a linked list example Updated 20090826 By Ben Golightly www.tophatstuff.co.uk www.funr.co.uk Note: You really, really don't want to sort any lists that contain strings!!! } Program Uses pure2d, keyset Const // Set mode to 1 for Random inital sort // Set mode to 2 for worst-case inital sort // Set mode to 3 for best-case inital sort mode = 1 NUMBER_OF_ITEMS = 10000 // That's 10,000 Type items = Record index: Integer //foo: String bar: Integer baz: Boolean EndType Var itemList: List of items anItem: ^items Procedure MergeSort(ByRef itemList: List of items) Var item1: ^items item2: ^items itemLast: ^items itemFirst: ^items tResult : List of items tLeft : List of items tRight: List of items i, count, middle: Integer Begin count = CountList(itemList) If count <= 1 then exit middle = (count / 2) - 1 Loop item1 through itemList If i <= middle then item2 = NewItem(tLeft) Cloneitem(item1, item2) Else item2 = NewItem(tRight) Cloneitem(item1, item2) Endif Inc(i) EndLoop MergeSort(tLeft) MergeSort(tRight) itemLast = LastItem(tLeft) itemFirst = FirstItem(tRight) If itemLast.index > itemFirst.index MergeSort_merge(tResult, tLeft, tRight) Else Loop item1 through tLeft item2 = NewItem(tResult) Cloneitem(item1, item2) Free(item1) EndLoop Loop item1 through tRight item2 = NewItem(tResult) Cloneitem(item1, item2) Free(item1) EndLoop Endif // return result Loop item1 through itemList Free(item1) EndLoop Loop item1 through tResult item2 = NewItem(itemList) Cloneitem(item1, item2) Free(item1) EndLoop End Procedure MergeSort_merge(ByRef tResult: List of items, ByRef tLeft: List of items, ByRef tRight: List of items) Var item1, item2 : ^items itemFirst1 : ^items itemFirst2 : ^items Begin While ( (CountList(tLeft) > 0) and (CountList(tRight) > 0) ) itemFirst1 = FirstItem(tLeft) itemFirst2 = FirstItem(tRight) If itemFirst1.index <= itemFirst2.index item1 = NewItem(tResult) Cloneitem(itemFirst1, item1) Free(itemFirst1) Else item1 = NewItem(tResult) Cloneitem(itemFirst2, item1) Free(itemFirst2) Endif Wend If (CountList(tLeft) > 0) Loop item1 through tLeft item2 = NewItem(tResult) Cloneitem(item1, item2) Free(item1) EndLoop Else Loop item1 through tRight item2 = NewItem(tResult) Cloneitem(item1, item2) Free(item1) EndLoop Endif End Procedure Cloneitem(item1: ^items, item2: ^items) Begin { item 2 } item2.index = item1.index //item2.foo = item1.foo item2.bar = item1.bar item2.baz = item2.baz End Function RandomString() : String Begin Case (Rand(1, 9)) of 1: result = "tea" 2: result = "coffee" 3: result = "beer" 4: result = "wine" 5: result = "rum" 6: result = "water" 7: result = "vodka" 8: result = "orange juice" 9: result = "apple juice" EndCase End Var i: Integer ms: Integer Begin // Create some example items... For i = 0 to NUMBER_OF_ITEMS anItem = NewItem(itemList) Case mode of 1: anItem.index = Rand(1, 100000) 2: anItem.index = 10000 - i 3: anItem.index = i EndCase //anItem.foo = RandomString() anItem.bar = Rand(1, 1000) anItem.baz = TRUE Next OpenScreen(800, 600, 32, FALSE) // Before For i = 3 to 40 anItem = IndexedItem(itemList, i) Text(10, i14, "Item index="+anItem.index+" bar="+anItem .bar) Next Text(10, 10, "Press Enter to sort "+NUMBER_OF_ITEMS+" items.") While (KeyHits(VK_RETURN) < 1) Flip Pause(1) Wend Cls Flip ms = Millisecs MergeSort(itemList) ms = Millisecs - ms // After For i = 3 to 40 anItem = IndexedItem(itemList, i) Text(10, i14, "Item index="+anItem.index+" bar="+anItem .bar) Next Text(10, 10, "Sorted "+NUMBER_OF_ITEMS+" items in "+ms+" millisecs. Press Enter to quit.") While (KeyHits(VK_RETURN) < 1) Flip Pause(1) Wend End --v Code for the Cobra programming language.

Comments

Mergesort a linked list

Comments