Binary Tree Sort

Binary Tree Sort is a simple, in its most primitive form, unstable sorting algorithm .

principle

With this algorithm , all elements to be sorted are inserted one after the other in a binary search tree . Then this tree is run through in-order , whereby all elements are found in sorted order .

In its very elementary form, the algorithm is not stable . If, however, instead of the most common search function Find, a variant is used that always searches down to the leaves either on the right or left, even if the key is available, the sorting algorithm becomes stable. This can be done by means of a comparison function , which in the event of equality always only returns the value +1 or only the value −1 instead of the return value 0 (with the same search function) or. a customized search function, such as B. FindDupGE .

complexity

The average complexity is , but in the worst case of an already sorted list it is . If a balanced binary search tree is used instead of the unbalanced one , the complexity is also in the worst case . ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle {\mathcal {O}}(n\log n)}$

Additional memory is required for the search tree to be built. ${\displaystyle {\mathcal {O}}(n)}$

Advantages and disadvantages

The algorithm is usually based on an existing implementation to management and manipulation of binary trees implemented. On this basis, it can be reduced to two simple work steps - creating the tree and the in-order run - and thus implemented very quickly.

The high time complexity in the worst case, the great effort for the individual operations , the additional memory requirements and the costly implementation in relation to its efficiency speak against it , if this has to be done from scratch.

However, if the aforementioned existing implementation provides balanced search trees, most of these disadvantages are eliminated.

Similar to Bubblesort , Binary Tree Sort is rarely used for real problems.

implementation

An example implementation in the Perl programming language :

 use Tree::Binary::Search;
 use Tree::Binary::Visitor::InOrderTraversal;

 # Legt die zu sortierenden Elemente fest
 my @zuSortierendeElemente = ( 'Birne', 'Apfel', 'Kirsche', 'Banane', 'Erdbeere', 'Zwiebel', 'Orange' );

 # Hier wird ein binärer Suchbaum erzeugt
 my $tree = Tree::Binary::Search->new;
 $tree->useStringComparison();

 # In der Schleife werden alle Elemente eingefügt
 for $element (@zuSortierendeElemente) {
        $tree->insert($element, $element);
 }

 # Der Baum wird schließlich in-order durchlaufen, und die Knoten werden in dieser Reihenfolge ausgegeben
 my $visitor = Tree::Binary::Visitor::InOrderTraversal->new;
 $tree->accept($visitor);
 print join(", ", $visitor->getResults()) . "\n";

Treesort

The binary tree sort algorithm is not to be confused with the treesort algorithm of Floyd or similar tree selection sorting algorithms. These algorithms do not build a binary tree element by element, but interpret the input to be sorted as a complete binary tree and have an asymptotically optimal running time of . The treesort algorithm is a predecessor of the Heapsort algorithm, whereby Heapsort has a better runtime and requires less additional memory. ${\displaystyle {\mathcal {O}}(n\log n)}$

Individual evidence

1. ^ Robert W. Floyd : Algorithm 113: Treesort . In: Communications of the ACM . tape 5 , no. 8 , August 1962, p. 434 .
2. ^ Donald E. Knuth : The Art of Computer Programming : Volume 3 Sorting and Searching . 2nd Edition. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0 , pp. 141-145 .
3. ↑ nist.gov