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
- !/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
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)
if __name__ == '__main__':
sleepsort([7, 2 ,100, 1, 9, 45, 2, 33, 7, 77, 25])
sleepsort([333, 222 ,112, 777, 901, 455, 256, 313, 125, 625, 825, 999, 316])