Sleep sort
Sleep sort | |
---|---|
Esecuzione dell'algoritmo | |
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | |
Caso ottimo temporalmente | |
Manuale |
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
V · D · M | ||
---|---|---|
Teoria | Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo | |
Algoritmi a scambio | Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort | |
Algoritmi di selezione | Selection sort · Heap sort · Smoothsort | |
Algoritmi ad inserimento | Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting | |
Algoritmi a fusione | Merge sort · Timsort | |
Algoritmi non comparativi | Radix sort · Bucket sort · Counting sort · Pigeonhole sort | |
Altri algoritmi | Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle | |
Algoritmi inefficienti | Stupid sort · Trippel sort |