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

{{draft task|Sorting Algorithms}}

{{Sorting Algorithm}}

A '''tree sort''' is a [[wp:sort algorithm|sort algorithm]] that builds a [[wp:binary search tree|binary search tree]] from the keys to be sorted, and then traverses the tree ([[wp:Tree traversal|in-order]]) so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.

 

* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981 A Comparative Study of Linked List Sorting Algorithms by Ching-Kuang Shene]

[[Sorting_algorithms#Sediment sort|Sediment sort]], [[Sorting_algorithms#bubble sort|bubble sort]], [[Sorting_algorithms#selection sort|selection sort]] perform very badly.

 

 

=={{header|J}}==

 

 

There's also the issue of how do we want to sort the sentences? Let's say we'll sort them in ascii order without normalization of the text (since that is simplest).

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.

 

(Processing time here is negligible - other than the time needed to fetch a copy of the book and render it as plain text ascii - but if we were careful to implement the efficiency recommendations of this task more in the spirit of whatever the task is presumably implying, we could probably increase the processing time by several orders of magnitude.)

 

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

5 3 7 9 1 -> 1 3 5 7 9

d c e b a -> a b c d e

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

<pre>'(1 3 5 7 9)</pre>

 

=={{header|Scheme}}==

{{libheader|Matchable}}

{{works with|Chicken Scheme}}

 

(define insert

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

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

 

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