PHPGangsta - Der praktische PHP Blog

PHP Blog von PHPGangsta


Zahlen sortieren mit Sleep Sort

with 4 comments

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.

Written by Michael Kliewe

Oktober 15th, 2012 at 10:19 am

4 Responses to 'Zahlen sortieren mit Sleep Sort'

Subscribe to comments with RSS or TrackBack to 'Zahlen sortieren mit Sleep Sort'.

  1. Sehr interessant. Ist die Differenz zwischen zwei übergebenen Werten sehr klein, wird es auch nicht funktionieren.

    Wadim

    15 Okt 12 at 10:31

  2. Interessant, aber trotzdem leider nutzlos.

    … Trifft es wohl ganz gut! :-)

    Oliver

    15 Okt 12 at 13:07

  3. Wow. Clevere Idee. Allerdings habe ich zwei Aussagen zu bemängeln. 😉

    „Das interessante an diesem Sleep Sort ist die algorithmische Laufzeit von O(n) bei n zu sortierenden Zahlen.“

    Hängt die Laufzeit des Algorithmus wirklich nur von der Anzahl der zu sortierenden Elemente ab? Ich bezweifle es, da eine Sequenz aus einer Million Einsen vermutlich schneller sortiert ist als die Sequenz 1, 1, 1000000.

    „[…] damit ist der Algorithmus theoretisch […] schneller als alle anderen Algorithmen.“

    Theoretisch ist er nicht schneller. Der Algorithmus ist nämlich nur auf Zahlen anwendbar. Es handelt sich also um „integer sorting“. Und für integer sorting gibt es Algorithmen mit linearer Laufzeit.

    Andre

    18 Okt 12 at 10:22

  4. Ich glaube, dass O(n) nicht stimmt: es setzt voraus, dass sleep() und das zugehörige Aufwecken O(1) ist. Wie schafft das Betriebssystem das? Intern muss das System ja die Prozesse in einer nach Ablaufzeit geordneten (=sortierten) Datenstruktur halten.

    Arno Hollosi

    22 Okt 12 at 13:16

Leave a Reply

You can add images to your comment by clicking here.