L'ordinamento per selezione (selection sort) in Python
In questa lezione implementerai il selection sort trovando ripetutamente l'elemento più piccolo e mettendolo al posto giusto.
Introduzione
Il problema
Alcuni algoritmi di ordinamento cercano di fare meno spostamenti possibile, e questo conta quando spostare un elemento è costoso. Il selection sort mostra una strategia diversa dal bubble sort: prima trova l'elemento giusto, poi lo sposta una volta.
Immaginalo così
Il selection sort è come formare una squadra per altezza. Scorri tutti quelli ancora in attesa, chiami il più basso e lo metti nel prossimo posto della fila. Poi scorri di nuovo gli altri per il successivo più basso, finché non resta nessuno.
for start in range(len(result)):📍 Il prossimo posto libero nella filaminimum = start🤔 Supponi che questa persona sia la più bassaresult[index] < result[minimum]🔎 Cerca tra gli altri qualcuno più bassoresult[start], result[minimum] = ...🔄 Sposta il più basso nel posto liberoIl selection sort trova ripetutamente l'elemento più piccolo nella parte non ordinata della lista e con uno scambio lo mette subito dopo la parte già ordinata. Fa O(n²) confronti ma al massimo n - 1 scambi.
Punti chiave
- Tutto ciò che sta a sinistra di
startè già ordinato, dastartin poi invece no. minimumricorda l'indice del valore più piccolo trovato finora nella parte non ordinata.- Il ciclo interno
for index in range(start + 1, len(result)):scorre il resto della lista. result[start], result[minimum] = result[minimum], result[start]fa uno scambio per posizione.
Quando si usa?
- Imparare le strategie di ordinamento e confrontarle.
- Situazioni in cui scrivere o spostare elementi è costoso, mentre i confronti costano poco.
- Trovare i k elementi più piccoli fermandosi dopo k passate.
Quando non serve
- Programmi veri:
sorted()è molto più veloce. - Dati quasi ordinati: il selection sort scorre comunque tutto, mentre l'insertion sort finisce in fretta.
Visualizzatore di L'ordinamento per selezione (selection sort) in Python
O(n²)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
Risultato dell'esecuzione
[11, 12, 22, 25, 64]
Spiegazione del codice
La variabile minimum registra la posizione del valore più piccolo nel resto della lista. Alla fine di ogni passata, quel valore viene scambiato nella posizione start. L'algoritmo ha sempre complessità O(n²) per i molti confronti, ma esegue al massimo n scambi.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Scambiare dentro il ciclo interno
Così ottieni un ordinamento più lento e confuso, con tanti scambi inutili.
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Minimo dell'Array Trova il valore più piccolo in una lista. Facile
- K-th Smallest Element Find the k-th smallest value without fully sorting. Media