Sleep sort: differenze tra le versioni

Versione delle 21:08, 14 mar 2013

Versione attuale delle 00:20, 12 ago 2025

(17 versioni intermedie di 10 utenti non mostrate)

Riga 1:

{{S|linguaggi di programmazione}}

{{Algoritmo|classe=[[Algoritmo di ordinamento]]|struttura dati=[[Array]]|tempo migliore=<math>O(max(input))</math>|tempo peggiore=<math>O(n^2+max(input))</math>|immagine=Sleep Sort Animation.gif|didascalia=Esempio di sleep sort ordina un array di interi casuali. L'asse orizzontale è l'indice dell'array e l'asse verticale è l'intero.}}

'''Sleep sort''' (in italiano: ordinamento assonnato) è un [[algoritmo di ordinamento]] basato sul tempo.

''Sleep sort'' lavora associando un contatore ad ogni elemento da ordinare.

ogniOgni contatore è inizialmente impostato con il valore dell'elemenoelemento 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 sarà ordinata.

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.

Riga 10 ⟶ 12:

== Codice ==

=== Bash ===

<sourcesyntaxhighlight lang ="bash">

#!/bin/bash

function f() {

Riga 22 ⟶ 24:

done

wait

</syntaxhighlight>

</source>

=== Python ===

<sourcesyntaxhighlight lang="python">

from time import sleep

from threading import Timer

Riga 45 ⟶ 47:

sleepsort([333, 222 ,112, 777, 901, 455, 256, 313, 125, 625, 825, 999, 316])

</syntaxhighlight>'''JAVA'''<syntaxhighlight lang="java">

</source>

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

}

}

</syntaxhighlight>

== Voci correlate ==

Riga 53 ⟶ 83:

{{Ordinamento}}

{{Portale|informatica}}

[[Categoria: Algoritmi di ordinamento]]

[[Categoria: Algoritmi di ordinamento]]