Smoothsort: differenze tra le versioni

Versione delle 17:46, 20 ago 2013

Versione delle 20:03, 1 ott 2013

Riga 23:

* 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 suisuoi 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.