Bubble sort

Algoritmo molto diffuso perché intuitivo ma con prestazioni scadenti.

Una passataUna passata

Una passata con ordinamenti di due elementi su tutte le n-1 coppie, all’interno di un array, provoca lo spostamento in alto della bolla più grande.

Sia

V=(20, 15, 10, 3)

alla fine della passata l’elemento più grande 20 si trova in ultima posizione

V=(15, 10, 3, 20)

Bubble sort

N passate, sulle n-1 coppie, ordinano sicuramente l’array

In realtà sono necessarie al massimo N-1 passate su N-i coppie (di ciascuna passata)

Osserva,,,

Bubble Sort

Miglioramenti?

Nel caso in cui il vettore risulti ordinato dopo un certo numero di passate è possibile interrompere l’esecuzione del While() introducendo la variabile ANCORA

Il numero di passate dipende solo da ANCORA

Se la variabile ANCORA non interviene si ha una passata in più.

Elimino la differenza N-i

La lunghezza del vettore dipende da UltimoScambio piuttosto che da UltimaCoppia

In questo modo le passate diventano più corte.

Il While…Do esterno diventa Repeat…Until

Elimino la variabile FINITO

Complessità dell’algoritmo

L’istruzione SCAMBIA() viene eseguita ogni volta che ha successo il controllo dell’istruzione If(...) Then.
Consideriamo il caso pessimo, cioè che succeda a ogni passo.
Quanti sono i controlli e le esecuzioni di SCAMBIA()?

i j TC TS
1 1…n-1 n-1 n-1
2 1…n-2 n-2 n-2
n-2 1…(n-(n-2))
1…2
2 2
n-1 1…(n-(n-1))
1…1
1 1

Quindi

TC(n)=TS(n)=(n-1)+(n-2)+...+1.

Quanto vale la somma?
Sappiamo che 1+2+...n=n(n+1)/2 e quindi

T(n)=(n-1)n/2=½n2-½n.

La complessità in tempo asintotica dell’algoritmo di ordinamento Bubble Sort è O(n2), sia per il numero di confronti che per il numero di scambi.

Nel caso ottimo, il vettore già ordinato, il numero di scambi è 0 ma rimane quadratico il numero di confronti.