Draft:Sleep sort

Sleep sort

Sleep sort is a time-based sorting algorithm. It works by associating a counter with each element to be sorted. Each counter is initially set with the value of the element to be sorted. The counters are then decremented at the same rate. When a given counter runs out, the associated item is added to the end of the list. Since the counters stop depending on the size of the elements, the list will be sorted once all the counters have stopped. This can be implemented using the operating system's timers, e.g. by forking a separate process for each element, or more simply using a vector of counters.

Codice

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

Python

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);  
    }  
}

JAVA

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

Voci correlate

• algoritmo di ordinamento