Bubble sort

Da Wikipedia, l'enciclopedia libera.
Bubble sort
Il Bubble sort in esecuzione su una lista di numeri
Bubble sort in esecuzione su una lista di numeri
Classe Algoritmo di ordinamento
Struttura dati Array
Caso peggiore temporalmente O(n^2)
Caso ottimo temporalmente O(n)
Caso medio temporalmente O(n^2)
Caso peggiore spazialmente O(n) totale, O(1) ausiliario
Ottimale No

In informatica il Bubble sort o bubblesort (letteralmente: ordinamento a bolle) è un semplice algoritmo di ordinamento dei dati. Il suo funzionamento è semplice: ogni coppia di elementi adiacenti della lista viene comparata e se sono nell'ordine sbagliato vengono invertiti di posizione. L'algoritmo scorre poi tutta la lista finché non vengono più eseguiti scambi, situazione che indica che la lista è ordinata.

L'algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati, con quelli più piccoli che "risalgono" verso le loro posizioni corrette all'interno della lista così come fanno le bollicine in un bicchiere di spumante. In particolare, alcuni elementi attraversano la lista velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente: i primi sono in gergo detti "conigli" e sono gli elementi che vengono spostati nella stessa direzione in cui scorre l'indice dell'algoritmo, mentre i secondi sono detti "tartarughe" e sono gli elementi che vengono spostati in direzione opposta a quella dell'indice.

Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo su cui sia definita una relazione d'ordine.

Il Bubble sort non è un algoritmo efficiente: ha una complessità computazionale dell'ordine di O(n^2) confronti, con n elementi da ordinare; si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità.[1]

Dell'algoritmo esistono numerose varianti, per esempio lo shaker sort.

Spiegazione astratta[modifica | modifica sorgente]

Il bubble sort è un algoritmo iterativo, ossia basato sulla ripetizione di un procedimento fondamentale. La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito (che si scorra l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante; nel seguito ipotizzeremo che lo si scorra partendo dall'inizio).

Per esempio, saranno confrontati il primo e il secondo elemento, poi il secondo e il terzo, poi il terzo e il quarto, e così via fino al confronto fra il penultimo e l'ultimo elemento. Ad ogni confronto, se i due elementi confrontati non sono ordinati essi vengono scambiati. Durante ogni iterazione almeno un valore viene spostato rapidamente fino a raggiungere la sua collocazione definitiva; in particolare, alla prima iterazione il numero più grande raggiunge l'ultima posizione dell'array.

Il motivo è semplice, e si può illustrare con un esempio. Supponiamo che l'array sia inizialmente disposto come segue:

15 6 4 10 11 2

Inizialmente 15 viene confrontato con 6, ed essendo 15>6, i due numeri vengono scambiati:

6 15 4 10 11 2

A questo punto il 15 viene confrontato col 4, e nuovamente scambiato:

6 4 15 10 11 2

Non è difficile osservare che, essendo 15 il numero massimo, ogni successivo confronto porterà a uno scambio e a un nuovo spostamento di 15, che terminerà nell'ultima cella dell'array. Per motivi analoghi, alla seconda iterazione è garantito che il secondo numero più grande raggiungerà la sua collocazione definitiva nella penultima cella dell'array, e via dicendo. Ne conseguono due considerazioni:

  1. se i numeri sono in tutto N, dopo N-1 iterazioni si avrà la garanzia che l'array sia ordinato;
  2. alla iterazione i-esima, le ultime i-1 celle dell'array ospitano i loro valori definitivi, per cui la sequenza di confronti può essere terminata col confronto dei valori alle posizioni N-1-i e N-i.

Ovviamente, a ogni iterazione può accadere che più numeri vengano spostati; per cui, oltre a portare il numero più grande in fondo all'array, ogni singola iterazione può contribuire anche a un riordinamento parziale degli altri valori. Anche per questo motivo, può accadere (normalmente accade) che l'array risulti ordinato prima che si sia raggiunta la N-1esima iterazione. Su questa osservazione sono basate alcune ottimizzazioni dell'algoritmo.

Analisi dell'algoritmo[modifica | modifica sorgente]

Il bubble sort effettua all'incirca \frac{N^2}{2} confronti ed \frac{N^2}{2} scambi sia in media che nel caso peggiore. Il tempo di esecuzione dell'algoritmo è \Theta(n^2).

Varianti e ottimizzazioni[modifica | modifica sorgente]

Esistono numerose varianti del bubblesort, molte delle quali possono essere definite ottimizzazioni nel senso che mirano a ottenere lo stesso risultato finale (l'ordinamento dell'array) eseguendo, in media, meno operazioni.

Un insieme di ottimizzazioni sono basate sull'osservazione che se, in una data iterazione, non avviene alcuno scambio, allora l'array è necessariamente ordinato e l'algoritmo può essere terminato anticipatamente (ovvero senza giungere alla N-1esima iterazione). Una tecnica di ottimizzazione può dunque essere applicata usando una variabile booleana (o equivalente) usata come "flag" che indica se l'iterazione corrente ha prodotto uno scambio. La variabile viene reimpostata a false all'inizio di ogni iterazione, e impostata a true solo nel caso in cui si proceda a uno scambio. Se al termine di una iterazione completa il valore della variabile flag è false, l'intero algoritmo viene terminato. Questa tecnica produce una riduzione del tempo medio di esecuzione dell'algoritmo, pur con un certo overhead costante (assegnamento e confronto della variabile flag).

Una seconda linea di ottimizzazione (che può essere combinata con la prima) è basata sull'osservazione che (sempre assumendo una scansione dell'array, per esempio, in avanti, e ordinamento crescente) se una data iterazione non sposta nessun elemento di posizione maggiore di un dato valore i, allora si può facilmente dimostrare che nessuna iterazione successiva eseguirà alcuno scambio in posizioni successive a tale valore i. L'algoritmo può dunque essere ottimizzato memorizzando l'indice a cui avviene l'ultimo scambio durante una iterazione, e limitando le iterazioni successive alla scansione dell'array solo fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo overhead (gestione della variabile aggiuntiva che indica la posizione di ultima modifica).

Un'altra variante già menzionata (lo shakersort) consente di ridurre la probabilità che si verifichi la situazione di caso peggiore (in cui tutte le ottimizzazioni precedentemente citate falliscono e quindi contribuiscono solo negativamente con i relativi overhead); vedi la voce relativa.

Conigli e tartarughe[modifica | modifica sorgente]

Come detto, la struttura dell'algoritmo porta ad avere elementi che si spostano verso la posizione corretta più velocemente di altri. Tutti gli elementi che si spostano nella stessa direzione di scorrimento dell'indice avanzano più velocemente di quelli che lo fanno in senso contrario. Riprendiamo l'esempio precedente. Data la lista

15 6 4 10 11 2

dopo la prima iterazione la disposizione dei numeri sarà:

6 4 10 11 2 15

Qui si osserva il "coniglio" 15 e la "tartaruga" 2: il primo numero, in una sola iterazione, ha attraversato tutta la lista posizionandosi nella sua collocazione definitiva. Il secondo, invece, durante la stessa iterazione è avanzato di una sola posizione verso la sua collocazione corretta.

Ovviamente sono stati effettuati diversi tentativi per eliminare le tartarughe ed aumentare l'efficienza del Bubble sort: l'algoritmo shaker sort risolve molto bene questo problema utilizzando un indice interno la cui direzione di scorrimento è invertita ad ogni passaggio; risulta più efficiente del Bubble sort ma paga un dazio in termini di complessità (O(n^2)). Il Comb sort compara elementi divisi da una grossa separazione potendo quindi spostare le tartarughe molto velocemente prima di procedere a controlli fra elementi via via sempre più vicini per rifinire l'ordine della lista (la sua velocità media è comparabile a quella di algoritmi molto più veloci quali il quicksort).

Pseudocodice[modifica | modifica sorgente]

Segue lo pseudocodice per la versione originale dell'algoritmo:

procedure BubbleSort( A : lista degli elementi da ordinare )
  scambio ← true
  while scambio
    scambio ← false
    for i ← 0 to length(A)-2  do
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        scambio ← true

Le prestazioni del Bubble sort possono essere leggermente incrementate tenendo conto del fatto che, dopo ogni comparazione (ed eventuali scambi), l'elemento più grande incontrato nel passaggio corrente si troverà nell'ultima posizione esaminata. Quindi, dopo il primo passaggio, il più grande elemento della lista sarà posizionato nell'ultima posizione: alla luce di questo, data una lista di lunghezza n, ln-simo elemento sarà spostato nella sua posizione finale dopo il primo passaggio, l(n-2)-simo (n-2 perché altrimenti si andrebbe a modificare una cella inesistente) elemento sarà posizionato nel secondo passaggio, e così via. Perciò ogni passaggio può essere di 1 passo più corto rispetto al precedente, evitando di scorrere tutta la lista ogni volta fino alla fine, dato che gli ultimi elementi sono già nella loro posizione definitiva e non devono essere più spostati. Possiamo rappresentare quanto detto con il seguente pseudocodice:

procedure BubbleSort( A : lista di elementi da ordinare)
  alto ← lenght(A) - 1
  while (alto > 0) do
    for i ← 0 to alto do
      if (A[i] > A[i + 1]) then       //scambiare il '>' con '<' per ottenere 
        swap ( A[i], A[i+1] )                  // un ordinamento decrescente
    alto ← alto - 1

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

  1. ^ Donald Kuth, The Art of Computer Programming Vol. 3, Addison Wesley, 1973.