Sorting algorithms/Tree sort on a linked list: Difference between revisions
Sorting algorithms/Tree sort on a linked list (view source)
Revision as of 17:19, 19 March 2019
, 5 years agoAdded Go
(Removed sentence about not adding to this task for the time being as we now have an agreed way forward.) |
(Added Go) |
||
Line 15:
Then construct a tree in situ: use the prev and next of that list as left and right tree pointers.<br>
Then traverse the tree, in order, and recreate a doubly linked list, again in situ, but of course now in sorted order.
=={{header|Go}}==
This is based on the Kotlin entry but has been adjusted to satisfy the revised task description.
<lang go>package main
import (
"container/list"
"fmt"
)
type BinaryTree struct {
node int
leftSubTree *BinaryTree
rightSubTree *BinaryTree
}
func (bt *BinaryTree) insert(item int) {
if bt.node == 0 {
bt.node = item
bt.leftSubTree = &BinaryTree{}
bt.rightSubTree = &BinaryTree{}
} else if item < bt.node {
bt.leftSubTree.insert(item)
} else {
bt.rightSubTree.insert(item)
}
}
func (bt *BinaryTree) inOrder(ll *list.List) {
if bt.node == 0 {
return
}
bt.leftSubTree.inOrder(ll)
ll.PushBack(bt.node)
bt.rightSubTree.inOrder(ll)
}
func treeSort(ll *list.List) *list.List {
searchTree := &BinaryTree{}
for e := ll.Front(); e != nil; e = e.Next() {
i := e.Value.(int)
searchTree.insert(i)
}
ll2 := list.New()
searchTree.inOrder(ll2)
return ll2
}
func printLinkedList(ll *list.List, f string, sorted bool) {
for e := ll.Front(); e != nil; e = e.Next() {
i := e.Value.(int)
fmt.Printf(f+" ", i)
}
if !sorted {
fmt.Print("-> ")
} else {
fmt.Println()
}
}
func main() {
sl := []int{5, 3, 7, 9, 1}
ll := list.New()
for _, i := range sl {
ll.PushBack(i)
}
printLinkedList(ll, "%d", false)
lls := treeSort(ll)
printLinkedList(lls, "%d", true)
sl2 := []int{'d', 'c', 'e', 'b', 'a'}
ll2 := list.New()
for _, c := range sl2 {
ll2.PushBack(c)
}
printLinkedList(ll2, "%c", false)
lls2 := treeSort(ll2)
printLinkedList(lls2, "%c", true)
}</lang>
{{out}}
<pre>
5 3 7 9 1 -> 1 3 5 7 9
d c e b a -> a b c d e
</pre>
=={{header|J}}==
| |||