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

=={{header|ATS}}==

Tree sort based on the algorithm at http://archive.today/WM83M

println! (dllist2list<int> lst)

end

{{out}}

=={{header|C}}==

#include <stdlib.h>

#include <time.h>

list_destroy(&list);

return 0;

{{out}}

=={{header|FreeBASIC}}==

{{trans|Yabasic}}

#define izda 1

#define dcha 2

showTree(1)

Print

{{out}}

<pre>eight five four nine one seven six ten three two</pre>

=={{header|Go}}==

This is based on the Kotlin entry but has been adjusted to satisfy the revised task description.

import (

lls2 := treeSort(ll2)

printLinkedList(lls2, "%c", true)

{{out}}

Implementation of doubly-linked list is given here [[Doubly-linked_list/Traversal#Haskell]]

import Data.Foldable

treeSort :: (Foldable t, Ord a) => t a -> [a]

<pre>λ> let l = mkDList [2,4,3,5,7,6,2,9]

With these choices, the task becomes:

sentences=: (<;.2~ '. '&E.@rplc&(LF,' !.?.')) finn

#sentences

14961

+/<:#@>C./:sentences

We have to swap almost every sentence, but 16 of them can be sorted "for free" with the swaps of the other sentences.

For that matter, inspecting the lengths of the cycles formed by the minimal arrangements of swaps...

... we can see that two of the sentences were fine right where they start out. Let's see what they are:

Very, all

So now you know.

Anyways, here we go:

right=: i.0

data=: i.0

if. y>:#data do.'' return. end.

(extract y{left),(y{data),extract y{right

This could be wrapped differently, but it's adequate for this task.

Example use would be something like:

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}}==

import java.util.*;

System.out.println(" after sort: " + list);

}

// Java provides a doubly-linked list implementation but it doesn't permit

}

}

{{out}}

=={{header|Julia}}==

data::T

left::Union{BTree, Nothing}

testtreesort(rand(1:99, 12))

<pre>

Unsorted: [1, 12, 15, 22, 28, 26, 69, 22, 1, 62, 73, 95]

=={{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:

import java.util.LinkedList

val ll2 = LinkedList(listOf('d', 'c', 'e', 'b' , 'a'))

ll2.treeSort()

{{out}}

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.

list2.append(s)

echo "Before sort: ", list2

{{out}}

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.

(define (tree-sort l)

(map car (ff->list

(print (tree-sort '(5 3 7 9 1)))

{{out}}

<pre>

=== version 1 ===

{{trans|Kotlin}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<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>

{{out}}

<pre>

=== version 2 ===

Following my idea of a revised task description, see talk page.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<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>

{{out}}

<pre>

{{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].

(require racket/match)

(tree-sort-itr '(() () ()) lst))

{{out}}

{{libheader|Matchable}}

{{works with|Chicken Scheme}}

(define insert

[(x (a . b)) (tree-sort-itr (insert a x) b)]

[_ "incorrect arguments or broken tree" ]))

=={{header|Wren}}==

{{libheader|Wren-llist}}

{{libheader|wren-sort}}

import "/sort" for Cmp

treeSort.call(ll)

var ll2 = DLinkedList.new(["d", "c", "e", "b", "a"])

{{out}}

=={{header|Yabasic}}==

// by Galileo, 04/2022

makeTree("one two three four five six seven eight nine ten")

showTree(1)

{{out}}

<pre>eight five four nine one seven six ten three two

=={{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.

var left,right,value;

fcn init(value){ self.value=value; }

}

}

File("bbb.zkl").pump(tree.add,fcn(line){ // 5,000 lines to 660 words

line.split(" ")[0].strip(); // take first word

});

{{out}}

<pre>