Algoritmo di ordinamento Selection sort in Python

Il Selection Sort è uno degli algoritmi di ordinamento più semplici e fondamentali. Anche se non è il più efficiente per grandi dataset, è un ottimo punto di partenza per chi si avvicina allo studio degli algoritmi di ordinamento. In questa guida esploreremo in dettaglio il selection sort, come funziona, come implementarlo in Python, e quali sono i suoi vantaggi e svantaggi.

Il selection sort è un algoritmo di ordinamento che suddivide la lista in due parti: una sotto-lista ordinata e una sotto-lista non ordinata. Il processo continua selezionando ripetutamente il minimo (o massimo, a seconda dell'ordine) elemento dalla parte non ordinata e spostandolo nella parte ordinata.

Funzionamento del selection sort

1. Individuazione del minimo: Si cerca il minimo elemento nella parte non ordinata della lista.

2. Scambio: Si scambia il minimo elemento trovato con il primo elemento della parte non ordinata.

3. Ripetizione: Si ripete il processo per il resto della lista, escludendo progressivamente la parte già ordinata.

4. Conclusione: L'algoritmo termina quando tutta la lista è ordinata.

Esempio di funzionamento selection sort

Consideriamo una lista [5, 3, 8, 4, 2].

Passata 1:

• Trova il minimo da [5, 3, 8, 4, 2] che è 2.

• Scambia 2 con 5, ottenendo [2, 3, 8, 4, 5].

Passata 2:

• Trova il minimo da [3, 8, 4, 5] che è 3.

• 3 è già al suo posto, quindi non si effettua alcuno scambio.

Passata 3:

• Trova il minimo da [8, 4, 5] che è 4.

• Scambia 4 con 8, ottenendo [2, 3, 4, 8, 5].

Passata 4:

• Trova il minimo da [8, 5] che è 5.

• Scambia 5 con 8, ottenendo [2, 3, 4, 5, 8].

La lista è ora ordinata.

Implementazione del Selection sort in Python

Implementare il Selection sort in Python è abbastanza diretto. Ecco un esempio di codice:

def selection_sort(lista):
    n = len(lista)
    for i in range(n):
        # Trova l'indice del minimo elemento nella parte non ordinata
        min_index = i
        for j in range(i+1, n):
            if lista[j] < lista[min_index]:
                min_index = j

        # Scambia il minimo elemento trovato con il primo elemento non ordinato
        lista[i], lista[min_index] = lista[min_index], lista[i]
    return lista

# Esempio di utilizzo
lista = [5, 3, 8, 4, 2]
ordinata = selection_sort(lista)
print("Lista ordinata:", ordinata)

Spiegazione del codice:

• for i in range(n): Questo ciclo esterno tiene traccia del primo elemento della parte non ordinata.

• min_index = i: Inizializza l'indice del minimo elemento.

• for j in range(i+1, n): Questo ciclo interno cerca il minimo elemento nella parte non ordinata.

• if lista[j] < lista[min_index]: Aggiorna l'indice del minimo elemento se trova un elemento più piccolo.

• lista[i], lista[min_index] = lista[min_index], lista[i]: Scambia il minimo elemento trovato con il primo elemento non ordinato.

Vantaggi e svantaggi del Selection sort

Vantaggi:

• Semplicità: Facile da capire e implementare.

• Minimo spazio aggiuntivo: Non richiede memoria aggiuntiva significativa oltre alla lista da ordinare.

• Stabile per piccoli dataset: Può essere efficiente per dataset molto piccoli o quasi ordinati.

Svantaggi:

• Efficienza: È inefficiente per grandi dataset. La sua complessità temporale è O(n²) nel caso peggiore e nel caso medio.

• Prestazioni: Spesso più lento di altri algoritmi di ordinamento più avanzati come il Merge Sort o il Quick Sort.

Confronto con altri algoritmi di ordinamento

Il Selection Sort, pur essendo facile da capire, è generalmente meno efficiente rispetto ad altri algoritmi di ordinamento come il Merge Sort, il Quick Sort, e l'Heap Sort. Questi algoritmi più avanzati hanno complessità temporali migliori e sono più adatti per grandi dataset.

Il Selection Sort e il Bubble Sort hanno entrambi una complessità temporale di O(n²), ma il Selection Sort effettua generalmente meno scambi, rendendolo leggermente più efficiente in termini di operazioni di scambio.

L'Insertion Sort è un altro algoritmo di ordinamento semplice che ha anche una complessità temporale di O(n²) nel caso peggiore. Tuttavia, l'Insertion Sort è spesso più efficiente del Selection Sort su piccoli dataset o dataset quasi ordinati, poiché riduce il numero di confronti necessari una volta che l'elemento corrente è posizionato correttamente.

Conclusione

Il selection sort è un algoritmo di ordinamento semplice e fondamentale che rappresenta un ottimo punto di partenza per chi inizia a studiare gli algoritmi di ordinamento. Anche se non è adatto per grandi dataset a causa della sua inefficienza, la sua facilità di implementazione e comprensione lo rende ideale per scopi didattici e per ordinare piccoli dataset.