Algoritmo di ordinamento Bubble sort in C

Il bubble sort è un semplice algoritmo di ordinamento che ripetutamente scorre la lista, o vettore, confronta i due elementi vicini e li scambia se si trovano nell'ordine sbagliato. Lo scorrimento attraverso gli elementi prosegue fino a quando la lista non è completamente ordinata.

Bubble sort è uno degli algoritmi di ordinamento più semplici da implementare, ma essendo molto inefficiente viene utilizzato principalmente a scopi didattici.

Fonte gif: Wikipedia

Analizzando la performance dell’algoritmo di ordinamento possiamo osservare che:

• nel caso peggiore, cioè quando tutti gli elementi contenuti sono da ordinare, presenta una complessità computazionale O(n²) dove n corrisponde al numero di elementi da ordinare nella lista.
• nel caso migliore, ovvero quando la lista è completamente ordinata e non si deve svolgere alcuno scambio, possiede una complessità computazionale O(n). In questo caso il bubble sort risulta più efficiente di altri algoritmi di ordinamento, in quanto l’abilità di verificare che la lista sia ordinata è implementata direttamente nell’algoritmo.

Esempio:
Consideriamo la seguente lista di numeri L = (5, 2, 6, 3) e applichiamo l’algoritmo di ordinamento bubble sort passo per passo.

Iniziamo partendo da sinistra confrontando due elementi alla volta:
(5, 2, 6, 3) -> (2, 5, 6, 3), avviene lo scambio dato che 5 > 2
(2, 5, 6, 3) -> (2, 5, 6, 3), rimane uguale dato che 5 < 6
(2, 5, 6, 3) -> (2, 5, 3, 6), scambio dato che 6 > 3

Una volta aver raggiunto la fine della lista si riparte dall’inizio:
(2, 5, 3, 6) -> (2, 5, 3, 6), invariato essendo già in ordine
(2, 5, 3, 6) -> (2, 3, 5, 6), scambio dato che 5 > 3
(2, 3, 5, 6) -> (2, 3, 5, 6)

Nonostante la lista sia già ordinata, l’algoritmo lo comprende solo dopo aver effettuato uno scorrimento in cui non avviene alcuno scambio.
(2, 3, 5, 6) -> (2, 3, 5, 6)
(2, 3, 5, 6) -> (2, 3, 5, 6)
(2, 3, 5, 6) -> (2, 3, 5, 6)

Implementazione di bubble sort in C

Una volta riempito o definito un array contenente dei numeri, passiamo all’ordinamento di tali elementi. Per implementare l'algoritmo di ordinamento bubble sort abbiamo bisogno di due cicli for, il primo viene utilizzato per ripetere N-1 volte il procedimento del secondo ciclo, che scorre la lista da sinistra a destra.
Ad ogni iterazione del secondo ciclo viene effettuato un controllo se l’elemento in posizione j è maggiore dell’elemento successivo (j+1), se verificato allora avviene uno scambio tra i due elementi. Per effettuare lo scambio dobbiamo avvalerci di una variabile temporanea che ci permette di compiere uno swap tra i due elementi.

  
#include <stdio.h> 
#define N 10

int main(){
	int i, j, temp;
	int lista[N] = {6, 2, 4, 7, 5, 1, 9, 3, 15, 22};

	for(i=0; i<N-1; i++){
		for(j=0; j<N-i-1; j++){
			if(lista[j]>lista[j+1]){
				temp = lista[j];
				lista[j] = lista[j+1];
				lista[j+1] = temp;
			}
		}
	}

	for(i=0; i<N; i++){
		printf("%d ", lista[i]);
	}

	return 0;
}


Output: 1 2 3 4 5 6 7 9 15 22 

Ottimizzazione: Bubble sort con sentinella

L’algoritmo bubble sort con sentinella è un’ottimizzazione della versione base di bubble sort, in particolare in questa versione viene interrotta l’esecuzione dell’algoritmo quando non avvengono più scambi. Per far ciò dobbiamo utilizzare una variabile k che ad ogni ciclo viene resettata a 0 e ogni volta che avviene una modifica viene posta a 1. Di conseguenza se non avviene uno scambio, k rimane a 0 e l’algoritmo esce dal ciclo esterno terminando l’ordinamento.

Questa versione dell’algoritmo bubble sort risulta essere più efficiente nel caso migliore, cioè quando la lista non è troppo disordinata, poiché è in grado accorgersi immediatamente se non avviene alcuno scambio evitando ulteriori scorrimenti.

  
#include <stdio.h>
#define N 10

int main(){
	int i, k, temp;
	int lista[N] = {6, 2, 4, 7, 5, 1, 9, 3, 15, 22};

	do{
		k=0;
		for(i=0; i<N-1; i++){
			if(lista[i]>lista[i+1]){
				temp = lista[i];
				lista[i] = lista[i+1];
				lista[i+1] = temp;
				k=1;
			}
		}
	}while(k == 1);

	for(i=0; i<N; i++){
		printf("%d ", lista[i]);
	}

	return 0;
}


Output: 1 2 3 4 5 6 7 9 15 22