Selection Sort in Python

Questo video accompagna la guida Selection Sort in Python e riprende i passaggi principali con una spiegazione più diretta e visuale.

Sintesi del video

Descrizione del funzionamento dell’algoritmo Selection Sort e implementazione dell’algoritmo in Python.

Punti trattati

• Strategia
• Esempio
• Iterazione 0
• Iterazione 1
• Iterazione 2

Testo di supporto

L’algoritmo di ordinamento Selection Sort è un miglioramento dell’algoritmo Bubble Sort poiché cerca di ridurre al minimo il numero di scambi richiesti per ordinare una lista di elementi.

La strategia adottata dall’algoritmo prevede un solo scambio per passaggio al posto degli N-1 richiesti dal Bubble Sort ; l’algoritmo Bubble Sort porta in cima l’elemento più grande attraverso un numero di piccoli passi, mentre l’algoritmo Selection Sort porta in cima l’elemento più grande ad ogni iterazione.

I passaggi eseguiti dal Selection Sort per ordinare una lista di N elementi prevedono:

• prima iterazione: spostamento dell’elemento più grande tra gli N elementi della lista
• seconda iterazione: spostamento dell’elemento più grande degli N-1 elementi della lista (non si considera più l’elemento più grande portato in cima all’iterazione precedente)
• terza iterazione: spostamento dell’elemento più grande degli N-2 elementi della lista (non consideriamo i due elementi della lista già ordinati)
• e così via per tutti gli altri elementi

Per ordinare una lista di N elementi, l’algoritmo Selection Sort ha bisogno di N-1 passaggi.

Per ordinare la lista [9, 8, 7, 6, 5], l’algoritmo Selection Sort prevede i seguenti passaggi.

Impostiamo l’ultimo elemento come elemento massimo ed iteriamo sulle altre posizioni

Impostiamo il penultimo elemento come elemento massimo ed iteriamo le altre posizioni, non considerando più l’ultima posizione, ordinata al passaggio precedente

La strategia descritta può essere applicata considerando l’elemento minimo della lista ad ogni passaggio portandolo in cima alla lista ed iterando per tutte gli indici della lista considerata.

Approfondimento scritto

Per comandi, esempi e passaggi completi puoi leggere l’articolo collegato: Selection Sort in Python .