Binarytreesort
Binary Tree Sort (im Deutschen auch Binarytreesort) ist ein einfacher, nicht stabiler Sortieralgorithmus.Prinzip
Bei diesem Algorithmus werden alle zu sortierenden Elemente nacheinander in einen binären_Suchbaum eingefügt. Anschließend wird dieser Baum in-order durchlaufen, wobei alle Elemente in sortierter Reihenfolge angetroffen werden.
Komplexität
Die durchschnittliche Komplexität beträgt ; im Worst_Case einer bereits sortierten Liste ist sie jedoch . Zudem wird für den aufzubauenden Suchbaum zusätzlicher Speicher benötigt.
Vor- und Nachteile
Der Algorithmus wird üblicherweise anhand einer existierenden Implementation zur Verwaltung und Manipulation von binären_Bäumen implementiert. Auf dieser Grundlage kann er auf zwei einfache Arbeitsschritte - das Anlegen des Baumes und den in-order-Durchlauf - reduziert werden und damit sehr schnell umgesetzt werden.
Gegen ihn spricht die hohe Zeitkomplexität im Worst Case und der große Aufwand für die einzelnen Operationen, der zusätzliche Speicherbedarf sowie die in Verhältnis zu seiner Effizienz aufwendige Implementierung, falls diese von Grund auf neu erfolgen muss.
Ähnlich wie Bubblesort wird Binary Tree Sort kaum bei realen Problemen eingesetzt.
Implementierungen
Perl
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 in dieser Reihenfolge ausgegeben
my $visitor = Tree::Binary::Visitor::InOrderTraversal->new;
$tree->accept($visitor);
print join(", ", $visitor->getResults()) . "\n";
Siehe auch
Liste von Algorithmen
