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'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.

CodiceModifica

BashModifica

<source lang ="bash">

  1. !/bin/bash

function f() {

   sleep "$1"
   echo "$1"

} while [ -n "$1" ] do

   f "$1" &
   shift

done wait </syntaxhighlight>

PythonModifica

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])

JAVA

public 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 correlateModifica