Tree sort

Binary Tree Sort ( in German also Binarytreesort ) is a simple, in its most primitive form is not stable sorting algorithm.

Principle

In this algorithm all the elements to be sorted are successively inserted into a binary search tree. Then, this tree is traversed in-order, all elements are encountered in sorted order.

In its very basic form, the algorithm is not stable. However, reference is made instead of the common search Find a variant to the leaves down also studied in existing key, such as FindDupGE, the sorting algorithm is stable.

Complexity

The average complexity is, in the worst case an already sorted list, it is however. However, if a balanced binary search tree is used instead of the unbalanced, the complexity is in the worst case.

For the search tree to be set up extra storage is required.

Pros and Cons

The algorithm is usually implemented using an existing implementation for the management and manipulation of binary trees. On this basis he can to two simple steps - will be reduced and will therefore be implemented very quickly - the creation of the tree and the in-order - flow.

Against him speaks of the high time complexity in the worst case and the large expenditure for each operation, the additional memory requirements as well as in relation to its elaborate implementation efficiency, if this must be done from scratch.

If the said existing implementation, however, balanced search trees available, falls off a large part of these disadvantages.

Similar Bubblesort Binary Tree Sort is hardly used in real problems.

Implementation

A sample implementation in the programming language Perl:

Use Tree :: Binary :: Search;   Use Tree :: Binary :: Visitor :: InOrderTraversal;     # Specifies the elements to be sorted   my @ zuSortierendeElemente = (' pear ', ' apple ', ' cherry ', ' banana ', ' strawberry ', ' onion ', ' Orange ');     # Here is a binary search tree is generated   my $ tree = Tree :: Binary :: Search- > new;   $ tree-> useStringComparison ();     # In the loop, all elements are inserted   for $ element ( @ zuSortierendeElemente ) {          $ tree-> insert ( $ element, $ element );   }     # The tree will eventually go through in-order, and the nodes are output in this order   my $ visitor = Tree :: Binary :: Visitor :: InOrderTraversal -> new;   $ tree-> accept ( $ visitor );   print join (", ", $ visitor -> getResults ()). "\ n"; treesort

The Binarytreesort algorithm is not to be confused with the treesort algorithm of Floyd or similar tree -selection - sort algorithms. These algorithms do not build element, a binary tree on, but interpret the input to be sorted as a complete binary tree and have an asymptotically optimal running time. The treesort algorithm is a predecessor of the heapsort algorithm, heapsort has a better running time and less extra memory.