Ordinamento a bolle

5.1 Definizione di ordinamento a bolle

L'ordinamento a bolle (Bubble Sort) è un semplice algoritmo di ordinamento che passa ripetutamente attraverso la lista, confrontando gli elementi adiacenti e scambiandoli se sono nell'ordine sbagliato. Questo processo continua finché la lista non è completamente ordinata.

Principio di funzionamento:

1. L'algoritmo passa attraverso la lista e confronta ogni coppia di elementi adiacenti.
2. Se gli elementi sono nell'ordine sbagliato (il primo è maggiore del secondo per l'ordinamento crescente) — vengono scambiati.
3. Questo processo si ripete per tutte le coppie di elementi nella lista.
4. Dopo ogni passaggio completo, l'elemento più grande "emerge" al suo posto (come una bolla sulla superficie dell'acqua), e quindi non partecipa più ai passaggi successivi.
5. Il processo si ripete finché la lista non è ordinata.

Complessità temporale e spaziale dell'ordinamento a bolle

Complessità temporale:

• Nel peggiore dei casi: O(n^2) — avviene quando gli elementi sono inizialmente ordinati in ordine inverso.
• Nel caso medio: O(n^2) — avviene per la disposizione casuale degli elementi.
• Nel migliore dei casi: O(n) — avviene quando gli elementi sono già ordinati (l'algoritmo può essere ottimizzato per questo caso, aggiungendo un controllo se uno scambio di elementi è avvenuto durante il passaggio).

Complessità spaziale:

O(1) — poiché l'algoritmo utilizza una quantità costante di memoria aggiuntiva (solo alcune variabili per memorizzare valori temporanei).

5.2 Implementazione dell'algoritmo

L'algoritmo "ordinamento a bolle" è il più semplice e primitivo algoritmo di ordinamento di una lista/array di elementi. Confronta semplicemente gli elementi a coppie e li scambia se necessario.

Versione 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Scambio degli elementi

print("Array ordinato:", array)
# Output: Array ordinato: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Il ciclo interno (evidenziato in verde) confronta l'elemento con il suo vicino a destra. E se necessario — scambia gli elementi.

Versione 2:

Possiamo immediatamente aggiungere un'ottimizzazione al nostro algoritmo: dopo il primo passaggio dell'algoritmo, l'elemento massimo si troverà all'estrema destra, quindi non deve essere considerato nel ciclo successivo.

Dopo la seconda iterazione ci saranno già 2 elementi massimi a destra, quindi il ciclo interno può essere eseguito fino a n - 1 - i, dove i è il numero di iterazioni passate nel ciclo esterno.

La nuova variante sarà così:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Scambio degli elementi

print("Array ordinato:", array)
# Output: Array ordinato: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Versione 3:

Anche l'array può essere quasi ordinato. Pertanto, possiamo aggiungere questa ottimizzazione: se il ciclo interno è passato attraverso tutti gli elementi ma non ha effettuato alcuno scambio, l'ordinamento è terminato.

In questa versione viene utilizzata la variabile swapped, che tiene traccia se c'è stato uno scambio di elementi durante l'ultima passata. Se dopo il passaggio attraverso l'array non ci sono stati scambi, significa che l'array è già ordinato e l'esecuzione di ulteriori iterazioni è inutile — non miglioreranno l'ordinamento. Quindi, la variabile swapped permette di accelerare significativamente l'algoritmo su array quasi ordinati, terminandolo in anticipo.

Implementazione dell'ordinamento a bolle in Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False  # Ottimizzazione: verifica se ci sono stati scambi
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # Scambio degli elementi
                swapped = True
        if not swapped:
            break  # Se non ci sono stati scambi, l'array è già ordinato
    return array

# Esempio di utilizzo:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Array ordinato:", sorted_array)
# Output: Array ordinato: [11, 12, 22, 25, 34, 64, 90]