Smoothsort: differenze tra le versioni

Versione delle 11:14, 17 mag 2010

Versione delle 02:03, 25 mag 2010

Riga 29:

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 efettuandoeffettuando 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.

<!--

==Operations==