Reine versus Hybridalgorithmen

Während die meisten Sortieralgorithmen „rein“ im Sinne der Umsetzung einer konkreten Idee sind, wurden schon seit den Sortierfrühzeiten Algorithmen, die Kompositionen / Konglomerate bereits bestehender Ideen sind, angestrebt. Selbstredend sind solche Algorithmen aufwendiger als ihre reinen (aber nicht notwendigerweise simplen) Pendants zu implementieren.

Es kann z.B. bei verschiedengroßen Teilarrays zwischen verschiedenen Sortieralgorithmen umgeschaltet werden („Umschalthybride“). Grund dafür ist, daß die Sortiergeschwindigkeit für unterschiedliche Elementeanzahlen unterschiedlich ist, sodaß für Sortierungen großer Elementeanzahlen der eine, für kleinere Abschnitte aber der andere Algorithmus schneller ist, oder manche funktionieren bei der Sortierung von Teilmengen nicht hinab bis zur kleinstmöglichen, für die Sortierung sinnvollen Elementeanzahl (die da 2 wäre, denn bei einem Element gibt es nichts mehr zu sortieren). Der vielleicht populärste und inzwischen weitverbreitetste Vertreter dieser „Umschalthybriden“ könnte Timsort sein, das zwar generell ein Naturalmergesort ist, bei kleinen Teilarrays jedoch Insertionsort verwendet.

Eine andere Möglichkeit besteht darin, intern einen nicht sehr effizienten (Kern-)Sortieralgorithmus von einem anderen (nicht zwangsläufig auch Sortier-)Algorithums zu „umhüllen  “ und so in Richtung wesentlicher Beschleunigung zu steuern. So beinhaltet Shell- intern Insertion- oder Bubblesort, Combsort beinhaltet Ripple-, Bubblesort oder Oetsort und die Shearsorts Oetsort. Umhüllende Hybridalgorithmen der besonderen Art sind die Radixsorts. Sie sind speziell, d.h., sie funktionieren nur mit ganzen Zahlen als Sortierelemente(schlüssel). Radixsort LSD (least significant digit) kann grundsätzlich sogar mit jedem stabilen internen Sortieralgorithmus kombiniert werden.

Eine dritte Hybridmöglichkeit besteht im Nacheinanderanwenden verschiedener Algorithmen. Da wäre z.B. das Merge-Insertion-Sort, das beide Algorithmen in dieser Reihenfolge anwendet und speziell dafür geschaffen wurde, die Anzahl der Vergleiche zu minimieren. Die Implementation dieses Algorithmus' im Sortierkino kann diese Eigenschaft leider nicht verdeutlichen. Patiencesort erstellt erst aufsteigende Teilarays „Runs“, was die Ordnung erhöht, um diese dann mit Naturalmergesort endgültig zu sortieren.

Kontaktformular