Rosetta Code

Sorting algorithms/Tree sort on a linked list: Difference between revisions

Page Discussion

Sorting algorithms/Tree sort on a linked list (view source)

Revision as of 12:33, 8 February 2024

2,965 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(4 intermediate revisions by 3 users not shown)
Line 19:
=={{header|ATS}}==
 
<syntaxhighlight lang="ats">(*
<lang ATS>(*
 
Tree sort based on the algorithm at http://archive.today/WM83M
Line 560:
println! (dllist2list<int> lst)
end
end</langsyntaxhighlight>
 
{{out}}
Line 571:
I see the task used to have something to do with Finnegan's Wake, and with counting cycles, etc. Here I simply sort a list of integers.
 
It is unlikely, in ATS, that someone would use doubly-linked lists as their canonical linked list implementation. Therefore sortingSorting a singly-linked list this way would be interesting, but I cannot think of a way to do it without allocating new nodes. Of course, a quicksort or mergesort can be done on a singly-linked list without allocating new nodes.
 
(Obviously, if one is sorting a ''non-linear'' linked list, it is in general necessary to allocate new nodes. However, it is not necessary to allocate any ''temporary'' nodes.)
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <time.h>
Line 684 ⟶ 686:
list_destroy(&list);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 694 ⟶ 696:
=={{header|FreeBASIC}}==
{{trans|Yabasic}}
<langsyntaxhighlight lang="freebasic">#define key 0
#define izda 1
#define dcha 2
Line 760 ⟶ 762:
showTree(1)
Print
Sleep</langsyntaxhighlight>
{{out}}
<pre>eight five four nine one seven six ten three two</pre>
Line 766 ⟶ 768:
=={{header|Go}}==
This is based on the Kotlin entry but has been adjusted to satisfy the revised task description.
<langsyntaxhighlight lang="go">package main
 
import (
Line 840 ⟶ 842:
lls2 := treeSort(ll2)
printLinkedList(lls2, "%c", true)
}</langsyntaxhighlight>
 
{{out}}
Line 855 ⟶ 857:
Implementation of doubly-linked list is given here [[Doubly-linked_list/Traversal#Haskell]]
 
<langsyntaxhighlight lang="haskell">{-# language DeriveFoldable #-}
import Data.Foldable
 
Line 893 ⟶ 895:
 
treeSort :: (Foldable t, Ord a) => t a -> [a]
treeSort = toList . mkTree</langsyntaxhighlight>
 
<pre>λ> let l = mkDList [2,4,3,5,7,6,2,9]
Line 930 ⟶ 932:
With these choices, the task becomes:
 
<langsyntaxhighlight Jlang="j"> finn=: fread '~user/temp/wake/finneganswake.txt'
sentences=: (<;.2~ '. '&E.@rplc&(LF,' !.?.')) finn
#sentences
14961
+/<:#@>C./:sentences
14945</langsyntaxhighlight>
 
We have to swap almost every sentence, but 16 of them can be sorted "for free" with the swaps of the other sentences.
Line 941 ⟶ 943:
For that matter, inspecting the lengths of the cycles formed by the minimal arrangements of swaps...
 
<langsyntaxhighlight Jlang="j"> /:~ #@>C./:sentences
1 1 2 2 4 9 12 25 32 154 177 570 846 935 1314 10877</langsyntaxhighlight>
 
... we can see that two of the sentences were fine right where they start out. Let's see what they are:
 
<langsyntaxhighlight Jlang="j"> ;:inv (#~(= /:~))sentences
Very, all
fourlike tellt. What tyronte power!</langsyntaxhighlight>
 
So now you know.
Line 958 ⟶ 960:
Anyways, here we go:
 
<langsyntaxhighlight Jlang="j">left=: i.0
right=: i.0
data=: i.0
Line 990 ⟶ 992:
if. y>:#data do.'' return. end.
(extract y{left),(y{data),extract y{right
)</langsyntaxhighlight>
 
This could be wrapped differently, but it's adequate for this task.
 
Example use would be something like:
<langsyntaxhighlight lang="j"> insert sentences
extract''</langsyntaxhighlight>
 
But task's the current url for Finnegan's Wake does not point at flat text and constructing such a thing would be a different task...
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">// TreeSortTest.java
import java.util.*;
 
Line 1,033 ⟶ 1,035:
System.out.println(" after sort: " + list);
}
}</langsyntaxhighlight>
 
<langsyntaxhighlight lang="java">// LinkedList.java
 
// Java provides a doubly-linked list implementation but it doesn't permit
Line 1,131 ⟶ 1,133:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,143 ⟶ 1,145:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">mutable struct BTree{T}
data::T
left::Union{BTree, Nothing}
Line 1,186 ⟶ 1,188:
 
testtreesort(rand(1:99, 12))
</langsyntaxhighlight>{{out}}
<pre>
Unsorted: [1, 12, 15, 22, 28, 26, 69, 22, 1, 62, 73, 95]
Line 1,194 ⟶ 1,196:
=={{header|Kotlin}}==
As I can't be bothered to download Finnegan's Wake and deal with the ensuing uncertainties, I've contented myself by following a similar approach to the Racket and Scheme entries:
<langsyntaxhighlight lang="scala">// version 1.1.51
 
import java.util.LinkedList
Line 1,238 ⟶ 1,240:
val ll2 = LinkedList(listOf('d', 'c', 'e', 'b' , 'a'))
ll2.treeSort()
}</langsyntaxhighlight>
 
{{out}}
Line 1,251 ⟶ 1,253:
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.
 
<langsyntaxhighlight Nimlang="nim">import lists, random
 
 
Line 1,295 ⟶ 1,297:
list2.append(s)
echo "Before sort: ", list2
echo "After sort: ", list2.treeSort()</langsyntaxhighlight>
 
{{out}}
Line 1,307 ⟶ 1,309:
Ol has builtin sorted key-value trees named "ff". We converting list into ff and back again as already sorted list. Only values (small integers, constants) and symbols are allowed.
 
<langsyntaxhighlight lang="scheme">
(define (tree-sort l)
(map car (ff->list
Line 1,315 ⟶ 1,317:
 
(print (tree-sort '(5 3 7 9 1)))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,324 ⟶ 1,326:
=== version 1 ===
{{trans|Kotlin}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 1,360 ⟶ 1,362:
<span style="color: #000000;">treeSort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">treeSort</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"dceba"</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,369 ⟶ 1,371:
=== version 2 ===
Following my idea of a revised task description, see talk page.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 1,464 ⟶ 1,466:
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"dceba"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"d"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"c"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"e"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"b"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"a"</span><span style="color: #0000FF;">})</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,481 ⟶ 1,483:
{{trans|Scheme}} -- this implementation illustrates differences in identifiers and syntaxes of Scheme and Racket's <code>match-lambda</code> family. [http://docs.racket-lang.org/reference/match.html <code>racket/match</code> documented here].
 
<langsyntaxhighlight lang="racket">#lang racket/base
(require racket/match)
 
Line 1,510 ⟶ 1,512:
(tree-sort-itr '(() () ()) lst))
 
(tree-sort '(5 3 7 9 1))</langsyntaxhighlight>
 
{{out}}
<pre>'(1 3 5 7 9)</pre>
 
=={{header|Raku}}==
{{trans|Go}}
<syntaxhighlight lang="raku" line># 20231201 Raku programming solution
 
class BinaryTree { has ($.node, $.leftSubTree, $.rightSubTree) is rw;
 
method insert($item) {
if not $.node.defined {
$.node = $item;
($.leftSubTree, $.rightSubTree)>>.&{ $_ = BinaryTree.new }
} elsif $item cmp $.node < 0 {
$.leftSubTree.insert($item);
} else {
$.rightSubTree.insert($item);
}
}
 
method inOrder(@ll) {
return unless $.node.defined;
$.leftSubTree.inOrder(@ll);
@ll.push($.node);
$.rightSubTree.inOrder(@ll);
}
}
 
sub treeSort(@ll) {
my $searchTree = BinaryTree.new;
for @ll -> $i { $searchTree.insert($i) }
$searchTree.inOrder(my @ll2);
return @ll2
}
 
sub printLinkedList(@ll, Str $fmt, Bool $sorted) {
for @ll -> $i { printf "$fmt ", $i }
$sorted ?? say() !! print "-> "
}
 
my @ll = <5 3 7 9 1>;
#my @ll = [37, 88, 13, 18, 72, 77, 29, 93, 21, 97, 37, 42, 67, 22, 29, 2];
printLinkedList(@ll, "%d", False);
my @lls = treeSort(@ll);
printLinkedList(@lls, "%d", True);
 
my @ll2 = <d c e b a>;
#my @ll2 = <one two three four five six seven eight nine ten>;
printLinkedList(@ll2, "%s", False);
my @lls2 = treeSort(@ll2);
printLinkedList(@lls2, "%s", True);
</syntaxhighlight>
You may [https://ato.pxeger.com/run?1=fZTPbtNAEMYvnPwUX4NBieRaxAGSKG2KeuBUiUN6Qwg58Riv6qyj3XVDFOVJONADvFSfprP-U8cmxZK93pn9Zn4zu9pff1R4lz88_M1NfD55fPV7lYZa41rIUO1uFRH2SEKNvuvLLCIPrp9SbBb50jrtVIkfST0fQGio7cxxAKzJJFkEITUp03eFofUAe-vhR8SQmUEZ1Y8oFpKiZy8_pQeXKISzxtH_P8F87r_dw_3OyqYIX9IWhyrGAZRqzl8Exmq9qXNd4F2b4CiP3ypjdhyK2qJjmhdUTvFp9eiLikj1P6Vp0yJFJlcSuUyJd6TdqTpUl7EJU6_gf3-T66TawEGj7IB2pAeHCXW-hGH3IuMiGrj1Dq6mUK2S4oR0O13o40zZ3Difc6P5EB0Jmq4Myl60fSUI52B5UMJUrbCGGmujhDQ3Qt5RdCN0QedhYRTceG08XGdZynGZm6KKuktURIjRswL0PGusaAoVrq6gw11_gLOzci16LO1ZgBIOXPnFB4wwxhTD-cx5Xdkv8XU09jCZeBiO-OVxHPDLtmDqYcq2YMgjz-269-z7aH1B6Q--zZyT5fXeRMz5OeQzx30pk2nO1tqik1pdi29VbrWVOLAVRFiBsETYVFDYM0kw2wwmsZscZ7lCLO4JWvyEpnuSIHuCIIVdSHJ-MnNgM-t_sYMOd_AC-LO-JC_vqeq6qq-tJw Attempt This Online!]
 
=={{header|Scheme}}==
Line 1,519 ⟶ 1,572:
{{libheader|Matchable}}
{{works with|Chicken Scheme}}
<langsyntaxhighlight Schemelang="scheme">(use matchable)
 
(define insert
Line 1,549 ⟶ 1,602:
[(x (a . b)) (tree-sort-itr (insert a x) b)]
[_ "incorrect arguments or broken tree" ]))
(tree-sort-itr '(() () ()) lst))</langsyntaxhighlight>
Usage: <langsyntaxhighlight Schemelang="scheme"> #;2> (tree-sort '(5 3 7 9 1))
(1 3 5 7 9)</langsyntaxhighlight>
 
=={{header|Wren}}==
Line 1,557 ⟶ 1,610:
{{libheader|Wren-llist}}
{{libheader|wren-sort}}
<langsyntaxhighlight ecmascriptlang="wren">import "./llist" for DLinkedList
import "./sort" for Cmp
 
class BinaryTree {
Line 1,601 ⟶ 1,654:
treeSort.call(ll)
var ll2 = DLinkedList.new(["d", "c", "e", "b", "a"])
treeSort.call(ll2)</langsyntaxhighlight>
 
{{out}}
Line 1,610 ⟶ 1,663:
 
=={{header|Yabasic}}==
<langsyntaxhighlight Yabasiclang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Tree_sort_on_a_linked_list
// by Galileo, 04/2022
 
Line 1,683 ⟶ 1,736:
makeTree("one two three four five six seven eight nine ten")
showTree(1)
print</langsyntaxhighlight>
{{out}}
<pre>eight five four nine one seven six ten three two
Line 1,690 ⟶ 1,743:
=={{header|zkl}}==
This code reads a file [of source code] line by line, and builds a binary tree of the first word of each line. Then prints the sorted list.
<langsyntaxhighlight lang="zkl">class Node{
var left,right,value;
fcn init(value){ self.value=value; }
Line 1,716 ⟶ 1,769:
}
}
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">tree:=Tree();
File("bbb.zkl").pump(tree.add,fcn(line){ // 5,000 lines to 660 words
line.split(" ")[0].strip(); // take first word
});
 
foreach word in (tree){ println(word) }</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/245185...352418"