Algoritmi Python

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.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dal formare una squadra al codice
for start in range(len(result)):📍 Il prossimo posto libero nella fila
minimum = start🤔 Supponi che questa persona sia la più bassa
result[index] < result[minimum]🔎 Cerca tra gli altri qualcuno più basso
result[start], result[minimum] = ...🔄 Sposta il più basso nel posto libero
Uno scambio per posizione, dopo aver scorso tutta la parte non ordinata.
In una frase

Il 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

  1. Tutto ciò che sta a sinistra di start è già ordinato, da start in poi invece no.
  2. minimum ricorda l'indice del valore più piccolo trovato finora nella parte non ordinata.
  3. Il ciclo interno for index in range(start + 1, len(result)): scorre il resto della lista.
  4. 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

Esegui codice →
main.py
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]))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Scambiare dentro il ciclo interno

Così ottieni un ordinamento più lento e confuso, con tanti scambi inutili.

Problema
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
Correzione
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.

Tutte le sfide