Sorting algorithms/Tree sort on a linked list: Difference between revisions
Sorting algorithms/Tree sort on a linked list (view source)
Revision as of 21:38, 5 November 2018
, 5 years ago→{{header|Phix}}
Line 189:
{{5,3,7,9,1}, " => ", {1,3,5,7,9}}
{"dceba", " => ", "abcde"}
</pre>
=== version 2 ===
Following my idea of a revised task description, see talk page.
<lang Phix>-- doubly linked list:
enum NEXT,PREV,DATA
constant empty_dll = {{1,1}}
sequence dll
procedure insert_after(object data, integer pos=1)
integer prv = dll[pos][PREV]
dll = append(dll,{pos,prv,data})
if prv!=0 then
dll[prv][NEXT] = length(dll)
end if
dll[pos][PREV] = length(dll)
end procedure
procedure append_node(integer node)
-- (like insert_after, but in situ rebuild)
integer prev = dll[1][PREV]
dll[node][NEXT] = 1
dll[node][PREV] = prev
dll[prev][NEXT] = node
dll[1][PREV] = node
end procedure
function dll_collect()
sequence res = ""
integer idx = dll[1][NEXT]
while idx!=1 do
res = append(res,dll[idx][DATA])
idx = dll[idx][NEXT]
end while
return res
end function
-- tree:
enum LEFT,RIGHT,KEY
function tree_insert(integer root, object item, integer idx)
if root=NULL then
return idx
else
integer branch = iff(item<dll[root][KEY]?LEFT:RIGHT)
dll[root][branch] = tree_insert(dll[root][branch],item,idx)
return root
end if
end function
procedure traverse(integer node)
if node!=NULL then
traverse(dll[node][LEFT])
integer right = dll[node][RIGHT]
append_node(node)
traverse(right)
end if
end procedure
bool detailed = true
procedure treeSort()
if detailed then
?{"initial dll",dll}
end if
object tree = NULL
integer idx = dll[1][NEXT]
while idx!=1 do
integer next = dll[idx][NEXT]
dll[idx][NEXT] = NULL
dll[idx][PREV] = NULL
tree = tree_insert(tree,dll[idx][DATA],idx)
idx = next
end while
dll[1] = {tree,0} -- (0 is meaningless, but aligns output)
if detailed then
?{"tree insitu",dll}
end if
dll[1] = empty_dll[1]
traverse(tree)
if detailed then
?{"rebuilt dll",dll}
end if
end procedure
procedure test(sequence s)
dll = empty_dll
for i=1 to length(s) do insert_after(s[i]) end for
?{"unsorted",dll_collect()}
treeSort()
?{"sorted",dll_collect()}
end procedure
test({5, 3, 7, 9, 1})
detailed = false
test("dceba")
test({"d","c","e","b","a"})</lang>
{{out}}
<pre>
{"unsorted",{5,3,7,9,1}}
{"initial dll",{{2,6},{3,1,5},{4,2,3},{5,3,7},{6,4,9},{1,5,1}}}
{"tree insitu",{{2,0},{3,4,5},{6,0,3},{0,5,7},{0,0,9},{0,0,1}}}
{"rebuilt dll",{{6,5},{4,3,5},{2,6,3},{5,2,7},{1,4,9},{3,1,1}}}
{"sorted",{1,3,5,7,9}}
{"unsorted","dceba"}
{"sorted","abcde"}
{"unsorted",{"d","c","e","b","a"}}
{"sorted",{"a","b","c","d","e"}}
</pre>
| |||