Algoritmo di ordinamento Bubble sort in Python

Il Bubble sort è uno degli algoritmi di ordinamento più semplici e conosciuti. Anche se non è il più efficiente per grandi dataset, la sua semplicità lo rende ideale per chi inizia a studiare gli algoritmi di ordinamento.

In questa guida esploreremo il bubble sort, come funziona, come implementarlo in Python, e quali sono i suoi vantaggi e svantaggi.

Il bubble sort è un algoritmo di ordinamento a confronto diretto che ordina una lista confrontando ripetutamente coppie di elementi adiacenti e scambiandoli se sono nell'ordine sbagliato. Questo processo continua finché la lista è ordinata.

Funzionamento del bubble sort

1. Confronto e scambio: Si confrontano gli elementi adiacenti della lista. Se un elemento è maggiore del successivo, si scambiano i due elementi.

2. Ripetizione: Questo processo viene ripetuto per ogni coppia di elementi adiacenti dall'inizio alla fine della lista.

3. Iterazione: Dopo ogni passata, l'elemento più grande "bolle" fino alla sua posizione corretta alla fine della lista. La passata successiva esclude l'ultimo elemento già ordinato.

4. Fine: L'algoritmo si conclude quando non sono più necessari scambi, indicando che la lista è ordinata.

Esempio di funzionamento bubble sort

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

Passata 1:

• Confronta 5 e 3: scambia ([3, 5, 8, 4, 2])

• Confronta 5 e 8: nessuno scambio ([3, 5, 8, 4, 2])

• Confronta 8 e 4: scambia ([3, 5, 4, 8, 2])

• Confronta 8 e 2: scambia ([3, 5, 4, 2, 8])

Passata 2:

• Confronta 3 e 5: nessuno scambio ([3, 5, 4, 2, 8])

• Confronta 5 e 4: scambia ([3, 4, 5, 2, 8])

• Confronta 5 e 2: scambia ([3, 4, 2, 5, 8])

Passata 3:

• Confronta 3 e 4: nessuno scambio ([3, 4, 2, 5, 8])

• Confronta 4 e 2: scambia ([3, 2, 4, 5, 8])

Passata 4:

• Confronta 3 e 2: scambia ([2, 3, 4, 5, 8])

La lista è ora ordinata.

Implementazione del bubble sort in Python

Implementare il bubble sort in Python è semplice. Ecco un esempio di codice:

def bubble_sort(lista):
    n = len(lista)
    for i in range(n):
        scambiato = False
        for j in range(0, n-i-1):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
                scambiato = True
        if not scambiato:
            break
    return lista

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

Spiegazione del codice:

• for i in range(n): Questo ciclo esterno tiene traccia del numero di passate attraverso la lista.

• scambiato = False: Questo flag serve per terminare l'algoritmo se non ci sono stati scambi in una passata, indicando che la lista è già ordinata.

• for j in range(0, n-i-1): Questo ciclo interno confronta e scambia gli elementi adiacenti.

• if lista[j] > lista[j+1]: Confronta gli elementi adiacenti e li scambia se sono nell'ordine sbagliato.

• if not scambiato: Se nessun elemento è stato scambiato nella passata, l'algoritmo termina.

Vantaggi e svantaggi del bubble sort

Vantaggi:

• Semplicità: Facile da capire e implementare.

• Stabile: Mantiene l'ordine relativo degli elementi uguali.

• Minimo Overhead: Non richiede memoria aggiuntiva significativa.

Svantaggi:

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

• Ridondanza: Effettua molte passate anche se la lista è quasi ordinata.

Ottimizzazione algoritmo ordinamento bubble sort

Esistono alcune ottimizzazioni che possono rendere il bubble sort leggermente più efficiente:

1. Flag di scambio: Utilizzare un flag per terminare l'algoritmo se non sono stati effettuati scambi in una passata.

2. Passate ridotte: Dopo ogni passata, il più grande degli elementi non ordinati si trova alla sua posizione corretta, quindi le successive passate possono escludere l'ultimo elemento già ordinato.

def bubble_sort_ottimizzato(lista):
    n = len(lista)
    for i in range(n):
        scambiato = False
        for j in range(0, n-i-1):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
                scambiato = True
        if not scambiato:
            break
    return lista

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

In questo esempio, l'uso del flag scambiato permette di terminare l'algoritmo non appena la lista è ordinata, riducendo il numero di passate necessarie.

Conclusione

Il bubble sort è un algoritmo di ordinamento semplice e didattico, ideale per chi inizia a studiare gli algoritmi di ordinamento. Sebbene non sia adatto per grandi dataset a causa della sua inefficienza, la sua facilità di implementazione lo rende un buon punto di partenza per comprendere i concetti di base dell'ordinamento. Con le ottimizzazioni giuste, il bubble sort può diventare leggermente più efficiente, ma per applicazioni pratiche su grandi dataset è consigliabile utilizzare algoritmi di ordinamento più avanzati come il Merge Sort o il Quick Sort.