Reine versus Hybridalgorithmen

Während die meisten Sortieralgorithmen „rein“ im Sinne der Umsetzung einer konkreten Idee sind, kamen in der letzen Zeit auch Sortieralgorithmen auf, die Kompositionen / Konglomerate bereits bestehender Ideen sind („umhüllende Sortieralgorithmen“). Selbstredend sind solche Algorithmen aufwendiger als ihre reinen (aber nicht notwendigerweise simplen) Pendants zu implementieren.

Grund für diese Hybriden 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 könnte Timsort sein. Auch die Shearsorts gehören dazu. Ein Hybridalgorithmus der besonderen Art ist 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.

Kontaktformular