Algoritmo di ordinamento Bubble Sort

Question

Potrei avere una spiegazione dell' algoritmo di ordinamento Bubble Sort ?

Answer 1

L'algoritmo di ordinamento bubble sort, effettua l’ordinamento di un array confrontando elementi adiacenti ed eventualmente scambiandoli. Poi effettua altre passate fin quando l’array è completamente ordinato.

L’algoritmo fondamentalmente parte da destra (il secondo ciclo è quello che fa gli scambi) confronta l’ultimo elemento, con il penultimo e se l’ultimo è < del penultimo li scambia.

Poi passa a confrontare il penultimo con il terzultimo e così via.. fino a confrontare il secondo con il primo.

A questo punto una prima passata dell'array è completa ed l'elemento più piccolo si troverà alla prima componente dell'array.

Si procede quindi con altre passate fermandosi al confronto fra il terzo e il secondo elemento dell'array.. e così  finché non viene ordinato completamente l'array.

Questo algoritmo si chiama Bubble sort perché come le bolle d'aria tendono a salire su, se vediamo l'array in verticale, gli elementi più piccoli man mano saliranno verso l'alto.

Di seguito il programma spiegato passo passo

void bubblesort(int a[], int n){

int i, j;

// N.B. n-1 è l'ultima componente dell'array.

for(i = 0; i < n - 1; i++) //scansiona tutto l'array tranne l'ultima componente: n - 1 escluso. Quindi fino al penultimo elemento.

      for (j = n - 1; j > i; j--) //j settato all'ultima componente e decresce ad ogni iterazione. Esce dal ciclo solo se j <= i

                  if (a[j] < a[j-1])  //se la componente corrente è più piccola della precedente, li scambia.

                          scambia(&a[j],&a[j-1]);                  

}

 

//la funzione scambia è così composta:

void scambia(int *a, int *b){ //richiede due indirizzi di memoria in entrata che verranno memorizzati in 2 puntatori.

int temp; //la variabile d'appoggio che memorizza temporaneamente il valore di a.

temp = *a;

*a = *b;

*b = temp;

}

//NB. l'asterisco * dei puntatori fa riferimento sempre al valore a cui punta il puntatore