Smoothsort: differenze tra le versioni

Versione delle 01:08, 18 mar 2017

Versione delle 13:08, 24 giu 2017

Riga 1:

{{Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

|imageimmagine = Smoothsort.gif

|captiondidascalia = Lo Smoothsort durante l'ordinamento di una lista già abbastanza ordinata ma con qualche elemento fuori sequenza.

|datastruttura dati = [[Array]]

|timetempo = <math>O(n\log n)</math>

|best-timetempo migliore = <math>O(n)</math>

|spacespazio = <math>O(n)</math> totale, <math>O(1)</math> ausiliario

|optimalottimale = Quando i dati sono già ordinati

|completo =

|complete=

}}

Riga 31:

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.

<!--

==Operations==

==Operations==

Ignoring (for the moment) Dijkstra's optimisations, two operations are necessary - increase the string by adding one element to the right, and decrease the string by removing the right most element (the root of the last heap), preserving the heap and string conditions.

Riga 68:

==Java implementation==

This code uses '''lo''' and '''hi''' as the bounds of the array ''inclusive''. Note that this is not the usual convention.

Riga 235 ⟶ 234:

{{ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]

[[Categoria:Heap]]