Ordinamento per selezione
Trova il valore più piccolo rimasto e lo porta con uno scambio nella posizione successiva. Fa pochissimi scambi, ma sempre lo stesso numero di confronti.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- no
- sì
Caso migliore: come cresce il tempo con la dimensione n della lista quando l'input è il più facile per questo algoritmo.
Caso medio: crescita tipica del tempo con n. Con n², raddoppiare il numero di valori quadruplica circa il tempo; n log n cresce molto meno.
Caso peggiore: la crescita sull'input più difficile. Utile quando la velocità non deve mai calare.
Spazio: quanta memoria extra serve oltre alla lista. 1 vuol dire poche variabili, n una copia della lista.
Stabile: due valori uguali mantengono il loro ordine originale. Conta quando si ordinano record in base a un solo campo.
Sul posto: ordina dentro la lista stessa, senza una seconda lista.
- confronto
- spostamento
- minimo attuale
- al suo posto finale
Confronti: 0 · coppie confrontate: 0 su 276 confrontata (più scuro = più spesso) in confronto ora Entrambi gli assi: valori dal più piccolo al più grande
Premi Riproduci: le linee mostrano come cresce il costo
Premi Riproduci o avanza passo passo.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli una lista invertita. Il numero di confronti resta esattamente uguale a quello di qualsiasi altra lista.
Come funziona
Scorre la parte non ordinata e trova il valore più piccolo. Lo scambia con il primo valore non ordinato, così un altro valore è al suo posto finale. Controlla sempre tutti i valori rimasti, anche quando la lista è già ordinata.
Quando conviene usarlo
Utile quando spostare i dati costa molto ma leggerli costa poco, perché fa al massimo uno scambio per posizione. In quasi tutti gli altri casi, la scelta semplice migliore è l'ordinamento per inserimento.