BUBBLE SORT

ALGORITMO:

PRIMA FASE


SECONDA FASE


TERZA FASE


ALGORTIMO OTTIMALE


SPIEGAZIONE ALGORTIMO

Questo algoritmo è valido solo per l'ordinamento di piccoli insiemi, infatti per insiemi vasti esistono metodi molto più efficienti. Il Bubblesort si comporta come segue:

PRIMA FASE: Nel ciclo interno gli elementi adiacenti vengono confrontati: se vet[i] > vet[j] si effettua lo scambio tra i valori. Il ciclo prosegue fino a quando i è uguale a n-1 e quindi termina solo quando tutti gli elementi sono stati confrontati. Poiché il confronto viene effettuato tra vet[i] e vet[i+1], l’ultimo confronto è quello fra vet[n-1] e vet[n].
Questa serie di confronti non è in generale sufficiente a ordinare l’array; la sicurezza dell’ordinamento è assicurata solo dalla ripetizione del ciclo n-1 volte.
In questo modo le istruzioni del ciclo interno vengono eseguite in tutto (n-1)^2 volte. Poiché nell’ordinamento ingenuo tali istruzioni venivano eseguite solo \frac{n(n-1)}{2} volte, questa versione del bubblesort risulta approssimativamente due volte più lenta dell’ordinamento ingenuo. In realtà il numero di volte in cui il ciclo interno va ripetuto dipende da quanto è disordinata la sequenza di valori iniziali. Si può quindi ottimizzare l’algoritmo facendo cessare l’esecuzione delle iterazioni quando un intero ciclo interno non ha dato luogo a nessuno scambio di valori tra vet[i] e vet[i+1].

SECONDA FASE: Si ottiene dunque una prima ottimizzazione dell’algoritmo interrompendo il ciclo esterno la prima volta che, per un’intera iterazione del ciclo interno, la clausola if non ha mai dato esito positivo.
All’interno del ciclo esterno la variabile booleana scambio viene inizializzata a FALSE; se almeno un confronto del ciclo interno dà esito positivo, allora a scambio viene assegnato il valore TRUE.
In pratica la variabile scambio è utilizzata come flag (bandiera): se il suo valore è TRUE il ciclo deve essere ripetuto, altrimenti il ciclo viene interrotto e si passa all’istruzione successiva.

TERZA FASE: Si può comunque ottenere un’ulteriore ottimizzazione, infatti ad ogni incremento di j, variabile che controlla il ciclo esterno, almeno gli ultimi j+1 elementi sono ordinati. Il fatto è valido in generale perché ogni singola iterazione del ciclo interno sposta verso il basso, nella posizione giusta, l’elemento più grande tra quelli non ancora ordinati.
Per ottimizzare l’algoritmo, ad ogni nuova ripetizione del ciclo esterno viene decrementato il valore del ciclo interno n:=n-1 in modo da diminuire di uno, di volta in volta, il numero di confronti effettuati.

ALGORITMO OTTIMALE: Ma è ancora possibile un’ulteriore ottimizzazione, infatti alla fine di ogni ciclo interno, gli elementi successivi a vet[p], elemento su cui è stato effettuato l’ultimo scambio, sono certamente ordinati. Possiamo quindi assegnare p a n ed eseguire il nuovo ciclo interno soltanto p volte.
Quest’ultima versione ottimizzata di bubblesort è, rispetto ad altri algoritmi di ordinamento, particolarmente conveniente se applicata a vettori che siano fin dall’inizio quasi ordinati, ovvero vettori in cui fin dall’inizio sono pochi gli elementi fuori posto.


COMPLESSITA’

Nel caso peggiore l’algoritmo necessita un numero dell’ordine di O(n^2) di passaggi, è uno dei più semplici da studiare e applicare ma risulta poco efficace se applicato a liste con molti elementi.
L’ottimizzazione dell’algoritmo, utilizzando la flag che controlla se durante l’iterazione è stato o no effettuato lo scambio, riduce la complessità a O(n) nel caso ottimo che si verifica soltanto se la sequenza risulta già ordinata.

---

Torna a Programmazione e Lab.