Post Image

Hai bisogno di ordinare un elenco di elementi omogenei (ad esempio numeri) all'interno di una lista in Python? Non sai che algoritmo utilizzare?

Se il tuo elenco non ha dimensioni enormi allora puoi utilizzare l'algoritmo di ordinamento Bubble Sort.

Il Bubble Sort, o algoritmo a bolla, è l'algoritmo più lento e meno efficiente tra tutti gli algoritmi utilizzabili per l'ordinamento. Tuttavia la sua logica molto intuitiva e la semplicità nella realizzazione software, lo eleggono a buon candidato nei casi nei quali abbiamo bisogno di un algoritmo rapido per ordinare piccole liste di elementi.

Strategia

La strategia di ordinamento dell'algoritmo Bubble Sort prevede lo spostamento, ad ogni iterazione, dell'elemento più grande della lista nell'ultima posizione considerata (target_index).

Alla prima iterazione è spostato in ultima posizione l'elemento più grande della lista, alla seconda iterazione è spostato il secondo elemento più grande, alla terza il terzo e così via.

Questa strategia richiede nel caso peggiore O(n²) e pertanto, per come abbiamo visto nell'articolo sulla notazione Big O, le presentazioni decadono al crescere della dimensione dell'input.

Tale algoritmo dovrebbe essere usato solamente con input molto piccoli.

Algoritmo

L'algoritmo di ordinamento Bubble Sort si basa su n-1 iterazioni necessarie per ordinare una lista di n elementi.

L'obiettivo di ogni singola iterazione è quello di portare nell'ultima posizione (target_index) l'elemento con il valore maggiore. Il target_index è l'ultima posizione della corrente iterazione. Il BubbleSort è composto da n-1 iterazioni ed ogni iterazione sposta il target_index di una posizione verso sinistra (decrementa l'indice).

Volendo ordinare una lista di 6 elementi [20,10,40,50,60,2] (che in Python saranno nelle posizioni da 0 a 5) avremo le seguenti iterazioni:

Iterazione Elementi considerati target_index Elemento spostato Lista
0 - - - [20,10,40,50,60,2]
1 6 5 60 [20,10,40,50,2,60]
2 5 4 50 [20,10,40,2,50,60]
3 4 3 40 [20,10,2,40,50,60]
4 3 2 20 [10,2,20,40,50,60]
5 2 1 10 [2,10,20,40,50,60]

La logica è quindi quella di spostare alla fine della lista l'elemento maggiore e, successivamente, non considerare più la cella ormai contenente l'elemento desiderato della lista.

Implementazione

L'implementazione dell'algoritmo Bubble Sort in Python è la seguente:

def bubble_sort(elements):
    target_index = len(elements) - 1
    for indexes in range(target_index, 0, -1):
        for index in range(indexes):
            element = elements[index]
            next_element = elements[index + 1]
            if element > next_element:
                elements[index] = next_element
                elements[index + 1] = element
    return elements

La precedente funzione prende come input una lista di elementi e restituisce la lista ordinata secondo l'algoritmo Bubble Sort.

Per invocare la funzione eseguire:

ordered_elements = bubble_sort([20, 19, 18, 17, 16, 15])
# ordered_elements memorizza la lista di elementi ordinati

Prestazioni

L'algoritmo Bubble Sort necessita di eseguire n-1 iterazioni ed eseguire x-1 confronti dove x rappresenta la posizione finale della lista da ordinare, per ogni iterazione.

Per tale motivo, nel caso peggiore, le prestazioni dell'algoritmo sono O(n²).

Conclusioni

Nell'articolo hai potuto vedere cos'è l'algoritmo di ordinamento Bubble Sort, come implementarlo e come utilizzarlo. L'algoritmo rappresenta una scelta nelle occasioni dove abbiamo la necessità di ordinare un numero esiguo di dati omogenei presenti su una lista Python.