Flashsort in Ruby

English

Es gibt auf github eine einfache Implementierung von Flashsort in Ruby, nachdem hier auf github schon eine Implementierung in C zu finden ist. Die C-Implementierung ist typischerweise schneller als die libc-Funktion qsort, aber letztlich hängt das von den Daten ab und davon, wie gut die metric-Funktion ist, die man zusätzlich zur Vergleichsfunktion bei Flashsort liefern muss. Man kann sich diese metric-Funktion als eine Art monotone Hashfunktion vorstellen, also gilt

Diese zusätzlich benötigte Funktion oder Methode ist nicht wirklich vorhanden, außer bei numerischen Werten, was den Einsatz von Flashsort etwas erschwert. Entscheidend für eine gute Performance ist eine gute metric-Funktion, allerdings sind bei typischen Text-Dateien schon ziemlich triviale Implementierungen ganz brauchbar.

In diesem Blogbeitrag sind weitere Sortieralgorithmen für Ruby gezeigt.