Sleep sort

Sleep sort
Esecuzione dell'algoritmo
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	$O(n^{2}+max(input))$
Caso ottimo temporalmente	$O(max(input))$

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[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 correlate

• algoritmo di ordinamento