Smoothsort
Lo Smoothsort durante l'ordinamento di una lista già abbastanza ordinata ma con qualche elemento fuori sequenza.
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle O(n\log n)}$
Caso ottimo temporalmente	${\displaystyle O(n)}$
Caso peggiore spazialmente	${\displaystyle O(n)}$ totale, ${\displaystyle O(1)}$ ausiliario
Ottimale	Quando i dati sono già ordinati
Manuale

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.

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 2ⁿ, 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.

• Commented transcription of EWD796a (PDF), su enterag.ch.

V · D · M Algoritmi di ordinamento
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

Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica