Sleep sort

Sleep sort (in italiano: ordinamento assonnato) è un algoritmo di ordinamento basato sul tempo.

Sleep sort lavora associando un contatore ad ogni elemento da ordinare. ogni contatore è inizialmente impostato con il valore dell'elemeno che deve essere ordinato. I contatori sono poi decrementati alla stessa velocità. Quando un dato contatore finisce, l'elemento associato viene aggiunto alla fine della lista. Poichè i contatori si fermano a seconda della grandezza degli elementi, la lista, una volta che tutti i contatori sono fermi sarà ordinata.

Può essere implementato utilizzando i timer del sistema operativo, per esempio facendo un fork di un processo separato per ogni elemento, o più semplicemente utilizzano un vettore di contatori.

Codice

Python

<source="python"> from time import sleep from threading import Timer

def sleepsort(values):

   sleepsort.result = []
   def add1(x):
       sleepsort.result.append(x)
   mx = values[0]
   for v in values:
       if mx < v: mx = v
       Timer(v, add1, [v]).start()
   sleep(mx+1)
   print(sleepsort.result)

</source>