Bubble sort
Bubble sort | |
---|---|
![]() | |
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | |
Caso ottimo temporalmente | Se si utilizza una guardia allora: |
Caso medio temporalmente | |
Caso peggiore spazialmente | totale, ausiliario |
Ottimale | No |
![Bubble sort colore modificato](http://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Bubblesort-edited-color.svg/512px-Bubblesort-edited-color.svg.png)
In informatica il Bubble sort o ordinamento a bolla è un semplice algoritmo di ordinamento di liste di dati. In esso l'insieme di dati viene scansionato, ogni coppia di elementi adiacenti viene comparata ed i due elementi vengono invertiti di posizione se sono nell'ordine sbagliato. L'algoritmo continua nuovamente a ri-eseguire questi passaggi su tutta la lista fino a quando non vengono più eseguiti scambi, situazione che indica che la lista è ordinata.[1]
Denominazione ed efficienza
[modifica | modifica wikitesto]L'algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati: quelli più piccoli "risalgono" verso un'estremità della lista, mentre quelli più grandi "affondano" verso l'estremità opposta della lista, come le bolle in un bicchiere contenente una bevanda frizzante. In particolare, alcuni elementi attraversano la lista velocemente (in gergo detti "lepri"), altri invece più lentamente (detti "tartarughe"). I primi vengono spostati nella stessa direzione in cui scorre l'indice dell'algoritmo, mentre i secondi nella direzione opposta.
Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di qualsiasi tipo per i quali sia definita una relazione d'ordine.
Il Bubble sort è più efficiente rispetto al più semplice algoritmo di Ordinamento Ingenuo perché, invece di continuare ad eseguire sempre fino alla fine i due cicli annidati, si interrompe appena si accorge di non effettuare più scambi quando l'ordinamento è già completo. Si tratta comunque di un algoritmo non particolarmente efficiente, presentando una complessità computazionale dell'ordine di O confronti, con n elementi da ordinare, pertanto il suo utilizzo si limita a scopi didattici in virtù della sua semplicità e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità.[2]
Dell'algoritmo esistono numerose varianti, per esempio lo shaker sort.
Spiegazione astratta
[modifica | modifica wikitesto]![](http://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif)
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; d'ora in poi 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 secondo il criterio prescelto, vengono scambiati di posizione. 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, alla seconda il secondo numero più grande raggiunge la penultima posizione, e così via.
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:
- se i numeri sono in tutto N, dopo N-1 iterazioni si avrà la garanzia che l'array sia ordinato;
- 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, ogni singola iterazione può contribuire anche a un riordinamento parziale degli altri valori. Anche per questo motivo, può accadere (e normalmente accade) che l'array risulti effettivamente ordinato prima che si sia raggiunta la N-1ª iterazione. Su questa osservazione sono basate le versioni ottimizzate dell'algoritmo.
Analisi dell'algoritmo
[modifica | modifica wikitesto]Il bubble sort effettua all'incirca confronti ed scambi sia in media che nel caso peggiore. Il tempo di esecuzione dell'algoritmo è .
Varianti e ottimizzazioni
[modifica | modifica wikitesto]Esistono numerose varianti del bubble sort, molte delle quali possono essere definite ottimizzazioni, in quanto mirano a ottenere lo stesso risultato finale (l'ordinamento dell'array) eseguendo, in media, meno operazioni, quindi impiegando meno tempo.
Un insieme di ottimizzazioni si basa sull'osservazione che se, in una data iterazione, non avviene più alcuno scambio, l'array è necessariamente ordinato e l'algoritmo può essere terminato anticipatamente (ovvero senza giungere alla N-1ª iterazione). Una tecnica di ottimizzazione può dunque essere applicata usando una variabile booleana (o equivalente) usata come "flag" che indica se nell'iterazione corrente si è eseguito almeno 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'array è ordinato e 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à scambi 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 wikitesto]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à (). 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 wikitesto]Di seguito viene riportato lo pseudocodice base relativo alla versione originale dell'algoritmo:
procedure BubbleSort(A:lista degli elementi da ordinare) scambio ← true while scambio do scambio ← false for i ← 0 to length(A)-1 do if A[i] > A[i+1] then swap( A[i], A[i+1] ) scambio ← true
Lo pseudocodice appena scritto sposta, ad ogni ciclo while, l'elemento più grande all'estrema destra.
Una versione alternativa potrebbe essere la seguente:
procedure BubbleSort(A:lista degli elementi da ordinare) for i ← 0 to length(A)-2 do for j ← i+1 to length(A)-1 do if A[j] < A[i] then swap( A[j], A[i] )
Questa versione, invece, sposta, ad ogni ciclo for esterno, l'elemento più piccolo all'estrema sinistra.
Ottimizzazioni
[modifica | modifica wikitesto]Le prestazioni del bubble sort possono essere leggermente migliorate tenendo conto del fatto che dopo la prima iterazione l'elemento più grande si troverà certamente nell'ultima posizione della lista, quella sua definitiva; alla seconda iterazione il secondo più grande si troverà in penultima posizione, quella sua definitiva, e così via. Ad ogni iterazione il ciclo dei confronti può accorciarsi di un passo rispetto al precedente evitando di scorrere ogni volta tutta la lista fino in fondo: all'n-esima iterazione si può quindi fare a meno di trattare gli ultimi n-1 elementi che ormai si trovano nella loro posizione definitiva. Possiamo rappresentare quanto detto con questo secondo pseudocodice:
procedure BubbleSort(A:lista di elementi da ordinare) scambio ← true n ← length(A) - 2 //poichè l'indice parte da 0 e devo fermarmi al penultimo elemento del vettore devo togliere 2 while (scambio) do scambio ← false for i ← 0 to n do if (A[i] > A[i + 1]) then //sostituire '>' con '<' per ottenere un ordinamento decrescente swap ( A[i], A[i+1] ) scambio ← true n ← n-1 //ad ogni passaggio il ciclo for si accorcia di un'iterazione
Un altro tipo di ottimizzazione deriva dall'osservazione che spesso, alla fine di una iterazione, non uno bensì due o più elementi si trovano nella loro posizione definitiva: tutti gli elementi che si trovano a valle dell'ultimo scambio effettuato risultano ordinati e si può evitare di trattarli ancora nell'iterazione successiva.
Possiamo rappresentare quanto detto con questo terzo pseudocodice:
procedure BubbleSort(A:lista di elementi da ordinare) n ← length(A) - 1 ultimoScambiato ← n while (ultimoScambiato > 0) do ultimoScambiato ← 0 for i ← 0 to n do if (A[i] > A[i + 1]) then //sostituire '>' con '<' per ottenere un ordinamento decrescente swap ( A[i], A[i+1] ) ultimoScambiato ← i n ← ultimoScambiato //ad ogni passaggio si accorcia il ciclo for fermandosi in corrispondenza dell'ultimo scambio effettuato
Il terzo pseudocodice accorcia ulteriormente, se possibile, il ciclo di for: mentre nello pseudocodice base ad ogni passaggio il ciclo si ripete sempre n-1 volte e nel secondo pseudocodice esso si accorcia progressivamente di una unità, nel terzo pseudocodice l'accorciamento può essere ancora più marcato dipendendo dal punto in cui si è verificato l'ultimo scambio.
Note
[modifica | modifica wikitesto]- ^ (EN) Newest 'bubble sort' Questions, su Stack Overflow.«Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.»
- ^ Donald Knuth, The Art of Computer Programming Vol. 3, Addison Wesley, 1973.
Voci correlate
[modifica | modifica wikitesto]Altri progetti
[modifica | modifica wikitesto]Wikibooks contiene implementazioni del bubble sort
Wikimedia Commons contiene immagini o altri file sul bubble sort
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Denis Howe, bubble sort, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
- (EN) Visualising Sorting Algorithms - Visualizzazione grafica di alcuni algoritmi di ordinamento
- (EN) Sorting Algorithm Animations - Animazione grafica di alcuni algoritmi di ordinamento