Selection sort

Il selection sort ordina una lista come molte persone ordinano le carte in mano: trova la più piccola, mettila per prima, poi trova la più piccola tra le rimanenti. Fa molti confronti ma pochissimi scambi, e il suo tempo di esecuzione dipende poco dall'ordine della lista.

Barre di altezze diverse in fase di ordinamento, con la parte ordinata a sinistra, la barra più piccola rimasta evidenziata e una freccia che la mostra mentre viene scambiata al suo posto
Barre di altezze diverse in fase di ordinamento, con la parte ordinata a sinistra, la barra più piccola rimasta evidenziata e una freccia che la mostra mentre viene scambiata al suo posto

L'idea

Dividi la lista in una parte ordinata a sinistra, all'inizio vuota, e una parte non ordinata a destra. Scorri la parte non ordinata e ricorda dove si trova il suo valore più piccolo. Scambia quel valore con il primo valore non ordinato: la parte ordinata è cresciuta di uno. Ripeti finché resta un solo valore, che deve essere il più grande.

Un esempio

Prendi 5, 1, 4, 2, 8. La prima passata scorre tutti e cinque i valori, trova 1 come il più piccolo e lo scambia con 5: 1, 5, 4, 2, 8. La seconda passata scorre 5, 4, 2, 8, trova 2 e lo scambia con 5: 1, 2, 4, 5, 8. La terza passata trova 4 già al suo posto e la quarta trova 5 già al suo posto, quindi non si sposta nulla. In tutto sono 4 + 3 + 2 + 1 = 10 confronti e solo 2 scambi. Il bubble sort ha bisogno di 4 scambi sulla stessa lista.

Sempre lo stesso numero di confronti

Per essere sicura di quale valore sia il più piccolo, la scansione deve guardare tutti i valori rimasti. La passata 1 fa n − 1 confronti, la passata 2 ne fa n − 2, e così via fino a 1, per un totale di n(n − 1)/2. Questo numero non dipende dalla lista: una lista ordinata costa esattamente tanti confronti quanti una inversa. Il selection sort non ha un arresto anticipato, perché una scansione che trova il valore più piccolo già in testa non ha imparato nulla sul resto.

Pochi scambi

Ogni passata fa al massimo uno scambio, quindi il selection sort non fa mai più di n − 1 scambi, e salta lo scambio quando il valore più piccolo è già al suo posto. Il bubble sort e l'insertion sort fanno tanti scambi quante sono le coppie fuori ordine, che possono essere circa n²/2. Quando scrivere un valore costa molto più che leggerne due, per esempio su una memoria che si consuma a ogni scrittura, il basso numero di scambi è un vantaggio.

Non stabile

Un ordinamento è stabile quando i valori uguali mantengono il loro ordine originale. Il selection sort non lo è, perché uno scambio a lunga distanza può portare un valore oltre uno uguale. In 2, 2, 1 la prima passata scambia il primo 2 con l'1, ottenendo 1, 2, 2 con i due 2 ora in ordine opposto. Una versione che sposta i valori intermedi invece di scambiare è stabile, ma muove molti più valori.

Provalo

Apri l'app e premi Avvia, oppure premi Passo per procedere un confronto alla volta. Il valore esaminato è evidenziato, il valore più piccolo finora ha un suo colore, e ogni passata termina con uno scambio verso la parte ordinata a sinistra. Prova una lista ordinata e una inversa: i confronti sono gli stessi, cambiano solo gli scambi.

Domande frequenti

Qual è la complessità temporale del selection sort?

O(n²) in ogni caso: esattamente n(n − 1)/2 confronti per n valori, qualunque sia il loro ordine. Fa al massimo n − 1 scambi e richiede solo O(1) memoria aggiuntiva.

Qual è la differenza tra selection sort e bubble sort?

Il bubble sort scambia i vicini man mano e può fermarsi prima quando una passata non fa scambi. Il selection sort ricorda solo dove si trova il valore più piccolo e fa un solo scambio alla fine di ogni passata. Il selection sort fa meno scambi; il bubble sort è più veloce sulle liste quasi ordinate.

Il selection sort è stabile?

No. Uno scambio può spostare un valore oltre un altro valore uguale, quindi valori uguali possono cambiare ordine. Si può renderlo stabile spostando i valori invece di scambiarli, il che richiede più spostamenti.

Che legame c'è tra heap sort e selection sort?

L'heap sort è un selection sort con un modo più rapido di trovare il valore successivo: tiene la parte non ordinata in un heap, così ogni selezione richiede circa log n passi invece di una scansione completa. Questo porta il totale a O(n log n).

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova il selection sort