Smoothsort
| Smoothsort | |
|---|---|
 | |
| Classe | Algoritmo di ordinamento |
| Struttura dati | Array |
| Caso peggiore temporalmente | |
| Caso ottimo temporalmente | |
| Caso peggiore spazialmente | totale, ausiliario |
| Ottimale | Quando i dati sono già ordinati |
In informatica lo Smoothsort[1][2] (metodo) è un algoritmo di ordinamento particolarmente indicato per ordinare liste di dati già parzialmente ordinate. Lo Smoothsort è una variante dell'Heap sort sviluppata da Edsger Dijkstra nel 1981: come l'Heap sort anche lo Smoothsort presenta il limite computazionale massimo pari a O(n log n). Lo Smoothsort, però, si avvicina ad un tempo O(n) se i dati in ingresso sono già parzialmente ordinati, mentre l'Heap sort mediamente impiega O(n log n), indifferentemente dal livello di ordinamento iniziale.
Analisi[modifica | modifica wikitesto]
La lista da ordinare viene divisa in una stringa di heap, ognuna delle quali di dimensione pari ad uno dei numeri di Leonardo L(n). Il processo di divisione è semplice: i nodi più a sinistra della lista sono divisi nell'heap più grande possibile, ed i rimanenti sono divisi allo stesso modo. Si può dimostrare che:
- qualsiasi lista di qualsiasi dimensione può essere divisa in sezioni di dimensione L(x).
- Verifica: banalmente, la più piccola sezione L(0) è 1.
- Non possono esserci 2 heap con la stessa dimensione. La stringa sarà dunque una stringa di heap con dimensioni forzatamente in ordine decrescente. Si può inoltre utilizzare un array di bit per tenere traccia di quali numeri di Leonardo sono usati come dimensioni degli heap (molte implementazioni utilizzano a tale scopo i bit meno significativi).
- Verifica: i numeri di Leonardo L(n) crescono meno rapidamente di 2n, per cui per ogni array ci sarà sempre un L(n) la cui dimensione sarà più grande della metà di quella dell'array. L'eccezione è l'array di dimensione 2, ma che può essere diviso in 2 heap di dimensione L(1) e L(0) che sono, per definizione, entrambi di valore 1.
- Non possono esserci 2 heap le cui dimensioni siano due numeri consecutivi di Leonardo, eccetto per gli ultimi due.
- Verifica: se fosse rimasto qualcosa, anche un singolo elemento, dopo aver usato due numeri di Leonardo consecutivi L(x+1) e L(x), potremmo averli combinati insieme per formare una porzione più grande di dimensione L(x+2). Ma siccome non lo abbiamo fatto, non può essere rimasto nulla dopo due heap di dimensione L(x+1) e L(x).
Ogni heap, la cui dimensione è L(x), è strutturata da sinistra a destra come un heap secondario di dimensione L(x-1), un heap secondario di dimensione L(x-2) ed un nodo radice, ad eccezione degli heap di dimensione L(1) e L(0) (che hanno valore 1 per definizione). Ogni heap mantiene la proprietà degli heap per cui un nodo radice è sempre maggiore o uguale ai nodi radice dei suoi heap figli (e quindi maggiore o uguale a tutti i nodi nei suoi heap figli), e la stringa di heap in toto mantiene la proprietà delle stringhe per cui il nodo radice di ogni heap è maggiore o uguale al nodo radice dell'heap alla sua sinistra.
Come conseguenza di ciò si ha che il nodo più a destra nella stringa è sempre maggiore o uguale a tutti gli altri nodi e, molto importante, un array che è già ordinato non richiede aggiustamenti per essere distribuito in una serie di heap validi. Questa è la caratteristica adattiva dell'algoritmo.
L'algoritmo è semplice. Si inizia dividendo la nostra lista non ordinata in un singolo heap di un elemento, seguito da una porzione non ordinata. Una lista di un elemento è banalmente una sequenza valida di heap: questa sequenza viene poi incrementata aggiungendo un elemento per volta alla sua destra, effettuando gli scambi del caso per tenere la proprietà della sequenza e la proprietà dell'heap, finché non ricopre l'intera lista iniziale.
A questo punto l'elemento più a destra della sequenza di heap sarà l'elemento più grande in qualsiasi heap e sarà perciò nella sua posizione corretta e definitiva. Si riducono quindi le serie di heap fino ad un singolo heap di un solo elemento rimuovendo il nodo più a destra (che sta a posto) ed effettuando un riarrangiamento per ripristinare la condizione di heap. Quando siamo tornati nella condizione di un singolo heap con un solo elemento, allora la lista è ordinata.
Note[modifica | modifica wikitesto]
Collegamenti esterni[modifica | modifica wikitesto]
- Commented transcription of EWD796a (PDF), su enterag.ch.
