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.