Selection sort: differenze tra le versioni

Versione delle 13:12, 4 feb 2019

Versione delle 07:14, 1 giu 2019

Riga 50:

a[i] ← a[posmin]

a[posmin] ← tmp

==Implementazioni==

Riga 81 ⟶ 80:

Un inconveniente dell'algoritmo di ordinamento per selezione è che il tempo di esecuzione dipende solo in modo modesto dal grado di ordinamento in cui si trova il file. La ricerca del minimo elemento durante una scansione del file non sembra dare informazioni circa la posizione del prossimo minimo nella scansione successiva. Chi utilizza questo algoritmo potrebbe stupirsi nel verificare che esso impiega più o meno lo stesso tempo sia su file già ordinati che su file con tutte le chiavi uguali, o anche su file ordinati in modo casuale.

Nonostante l'approccio ''brutale'' adottato, l'ordinamento per selezione ha un'importante applicazione: poiché ciascun elemento viene spostato al più una volta, questo tipo di ordinamento è il metodo da preferire quando si devono ordinare file costituiti da record estremamente grandi e da chiavi molto piccole. Per queste applicazioni il costo dello spostamento dei dati è prevalente sul costo dei confronti e nessun algoritmo è in grado di ordinare un file con spostamenti di dati sostanzialmente inferiori a quelli dell'ordinamento per selezione.

== Altri progetti ==

{{interprogetto|commons=Category:Selection sort|b=Implementazioni di algoritmi/Selection sort|b_oggetto=implementazioni|b_preposizione=di}}

{{ordinamento}}