Bubble Sort in Python

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

Sintesi del video

Bubble Sort è un algoritmo di ordinamento a bolla. In questo articolo vedremo cos’è, come funziona, e come implementarlo in Python.

Punti trattati

• Strategia
• Algoritmo
• Implementazione
• Prestazioni

Testo di supporto

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.

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.

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:

Approfondimento scritto

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