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'elemento 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 sarà ordinata una volta che tutti i contatori sono fermi.
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 Bash #!/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 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])JAVApublic class SleepSort { public static void main(String[] args) { int[] ints = {1,4,7,3,8,9,2,6,5}; SortThread[] sortThreads = new SortThread[ints.length]; for (int i = 0; i < sortThreads.length; i++) { sortThreads[i] = new SortThread(ints[i]);
for (int i = 0; i < sortThreads.length; i++) { sortThreads[i].start();
class SortThread extends Thread{ int ms = 0; public SortThread(int ms){ this.ms = ms;
public void run(){ try { sleep(ms*10+10); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace();
System.out.println(ms);
Voci correlate
algoritmo di ordinamento
Categoria:Algoritmi di ordinamento