Bubble sort base
Bubble sort ottimizzato

Bubble sort
Complessità

 

Bubble sort, versione "base"

Facile da implementare, efficiente per piccoli inputs e operante in-place il bubblesort agisce considerando coppie adiacenti di elementi, e scambiandole se non rispettano la relazione d'ordine desiderata.

Se in una scansione del vettore non si effettuano scambi, significa che il vettore è ordinato.

Si chiama ordinamento a bolla perché dopo la prima scansione del vettore, l'elemento massimo si porta in ultima posizione (gli elementi più piccoli salgono come "bolle" verso le posizioni iniziali del vettore).

void bubbleSort(vector v, int start, int end) {
int swap, i, temp;

swap = FALSE;
for (i = start; i < end; i++) {
if (v[i] > v[i+1]) {
swap = TRUE;
temp = v[i];
v[i] = v[i+1];
v[i+1] = temp;
}
}
if (swap) bubbleSort(v, start, end-1);
}
 
 

Esempio d'uso

Scrivi 5 numeri interi: 9 3 2 6 7

9 3 2 6 7
3 2 6 7 9
2 3 6 7 9
2 3 6 7 9

Il vettore ordinato è: 2 3 6 7 9

Nota: l'ultimo passaggio è inutile!!


Bubble sort ottimizzato

Utilizza una variabile ausiliaria per tenere traccia della posizione in cui è stato effettuato l'ultimo scambio.

Ad ogni iterazione si esclude la parte finale del vettore (che è certamente già ordinata).

void bubble(vector v, int start, int end) {
int i, swap = start-1, temp;

for (i = start; i < end; i++) {
if (v[i] > v[i+1]) {
swap = i;
temp = v[i];
v[i] = v[i+1];
v[i+1] = temp;
}
}

if (swap > start) bubble(v, start, swap);

}
 

Esempio d'uso

Scrivi 5 numeri interi: 9 3 2 6 7

9 3 2 6 7
3 2 6 7 9
2 3 6 7 9

Il vettore ordinato è: 2 3 6 7 9

L'ultimo passaggio inutile è stato eliminato.


Complessità dell'algoritmo bubble sort

La complessità dipende dai particolari dati di ingresso.

Caso migliore: Vettore già ordinato.

Caso peggiore: Vettore ordinato in senso decrescente.
n° confronti
n-1
n-2 
...
3 
2
1 
scambi
n-1 
n-2
... 
3
2 
1
iterazione
1 
2
... 
n-3
n-2 
n-1
e quindi:

time = 2 * S in-1  (n- i) = n*(n-1) = O(n2)

Caso medio: Vettore ordinato a caso

Comparo il primo elemento con gli altri n-1 elementi. L'algoritmo compirà n-1 passi per muovere il più piccolo elemento in cima alla lista.
Il secondo elemento è comparato con gli altri n-2 elementi perchè il primo non lo tocco più. Qui si compiranno n-2 passi per portare il più piccolo elemento trovato nel secondo posto della lista.
Estendendo questo processo all'intera lista si avranno:

(n-1)+(n-2)+(n-3)+...+1 = n(n-1)/2 passi.

Ad esempio con un array di 16 elementi si avranno 16 x 15 / 2 = 120 passi.


Il bidirectional bubble sort della Sun

E' semplicemente un bubble sort leggermente ottimizzato in modo da avere due ordinamenti contemporaneamente: uno che comincia da sopra e uno da sotto.
Il tutto è realizzato con due cicli for invece che con uno: for (j = st; j < limit; j++) e for (j = limit; --j >= st;). Ecco il listato e la pagina di Sun con l'applet.


back