PHPGangsta - Der praktische PHP Blog

Sortieralgorithmen werden nicht dauernd neu erfunden, man kennt aus den letzten Jahrzehnten bereits einige dutzend gute Algorithmen, und schon lange ist kein besserer mehr „erfunden“ worden.

Letztes Jahr kam ein Unbekannter daher und präsentierte dieses einfache Programm, den sogenannten Sleep Sort:

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

Ein Bash-Script, das die übergebenen Parameter sortiert, und zwar indem pro Parameter i ein eigener Unterprozess gestartet wird, der so viele Sekunden wartet wie der Wert, den i hat. Wenn man also die Zahlenfolge 7,3,5,9 übergibt, werden 4 Kindprozesse gestartet, wobei der erste mit der 7 sieben Sekunden schläft und dann 7 ausgibt, der zweite mit der 3 drei Sekunden schläft und dann 3 ausgibt usw.  Nach 9 Sekunden hat man die 4 Zahlen sortiert ausgegeben.

Die Performance ist natürlich ziemlich schlecht, auch wenn man statt einer Sekunde nur eine Tausendstel Sekunde wartet. Außerdem gibt es Probleme mit negativen Zahlen und sehr großen Zahlen.

Das interessante an diesem Sleep Sort ist die algorithmische Laufzeit von O(n) bei n zu sortierenden Zahlen. Jede Eingabeziffer muss nur einmal angefasst werden und dann ausgegeben werden, damit ist der Algorithmus theoretisch (wenn man die Anzahl Schleifen etc. zählt) schneller als alle anderen Algorithmen. In der Praxis ist er natürlich nicht einsetzbar, aber trotzdem eine sehr interessante Idee, das Problem zu lösen.

Von Freiwilligen wurde der Algorithmus bereits in über 20 Programmiersprachen nachgebaut. Interessant, aber trotzdem leider nutzlos.