Anonymous user
Sorting algorithms/Tree sort on a linked list: Difference between revisions
Sorting algorithms/Tree sort on a linked list (view source)
Revision as of 18:53, 7 June 2021
, 3 years ago→{{header|Nim}}
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 551:
d c e b a -> a b c d e
</pre>
=={{header|Nim}}==
Inspired by C and Java solutions.
As Nim standard library provides a doubly linked list implementation which allows to access to the "prev" and "next" fields, we used it. So, we had only to write the transformation from list to tree and conversely.
<lang Nim>import lists, random
func treeInsert[T](tree: var DoublyLinkedNode[T]; node: DoublyLinkedNode[T]) =
if tree.isNil: tree = node
elif node.value < tree.value: tree.prev.treeInsert(node)
else: tree.next.treeInsert(node)
func listFromTree[T](list: var DoublyLinkedList[T]; node: DoublyLinkedNode[T]) =
if node.isNil: return
let prev = node.prev
let next = node.next
list.listFromTree(prev)
list.append(node)
list.listFromTree(next)
func treeSort[T](list: DoublyLinkedList[T]): DoublyLinkedList[T] =
var list = list
if list.head == list.tail: return list
var n = list.head
var root: DoublyLinkedNode[T] = nil
while not n.isNil:
var next = n.next
n.next = nil
n.prev = nil
root.treeInsert(n)
n = next
result = initDoublyLinkedList[T]()
result.listFromTree(root)
randomize()
var list1 = initDoublyLinkedList[int]()
for i in 0..15: list1.append(rand(10..99))
echo "Before sort: ", list1
echo "After sort: ", list1.treeSort()
echo()
var list2 = initDoublyLinkedList[string]()
for s in ["one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"]:
list2.append(s)
echo "Before sort: ", list2
echo "After sort: ", list2.treeSort()</lang>
{{out}}
<pre>Before sort: [27, 33, 51, 66, 34, 56, 81, 78, 32, 63, 78, 48, 71, 66, 30, 49]
After sort: [27, 30, 32, 33, 34, 48, 49, 51, 56, 63, 66, 66, 71, 78, 78, 81]
Before sort: ["one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"]
After sort: ["eight", "five", "four", "nine", "one", "seven", "six", "ten", "three", "two"]</pre>
=={{header|Ol}}==
| |||