Bubble Sort

Il Bubble Sort è un algoritmo di ordinamento per scambio.
Nel Bubble Sort si parte dall'ultimo elemento dell'array e lo si confronta con il precedente, se è più piccolo lo si scambia e si riparte dall'ultimo elemento, se è più grande si procede con il confronto.

Dunque ad ogni ciclo si confronta l'ultimo elemento con tutti i precedenti non ancora ordinati. Se il confronto risulta vero si imposta un flag indicante che l'array non è ancora ordinato.

Funzionamento del Bubble Sort

L'algoritmo funziona con due cicli for. Il primo itera tante volte quanti elementi ci sono nell'array, partendo da 0 fino a n-1. Mentre il for interno parte dall'ultimo elemento e scorre indietro fino all'indice raggiunto dal primo for.

Passaggi:

• Inizializzare il flag  ordinato a zero
• Si entra nel primo for controllato da n-1 e dal flag ordinato diverso da 1
• Si entra nel secondo ciclo, partendo dall'ultimo elemento scorrendo indietro l'array fino all'indice J o finché non c'è uno scambio da fare.
• Se si verifica uno scambio si assegna zero al flag ordinato, così che il ciclo for esterno continui l'iterazione

Scambiare due elementi

La maggior parte degli algoritmi di ordinamento richiedono di scambiare due elementi in diverse posizioni dell'array, e per questo si scrive una semplice funzione di swap().
Swap( ), prende in input gli indici delle posizioni da scambiare e un riferimento all'array.

Diagramma di flusso

Codice

File Header bubble_sort.c

void Swap(int i, int j, int a[])
{
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void BubbleSort(int v[], int n)
{
    int ordinato = 0;
    int i;
    int j;

    for (j = 0; j &lt n - 1 && ordinato == 0; j++)
    {
        ordinato = 1;
        for (i = n - 1; i > j; i--)
        {
            if (v[i] &lt v[j])
            {
                Swap(i, j, v);
                ordinato = 0;
            }
        }
    }
}

Programma principale main.c

#include&ltstdio.h&gr
#include&ltstdlib.h&gr
#include "bubble_sort.h"


int main(void)
{
    int n;
    int i;
    int *p;
    
    do{
         printf("Quanti elementi deve avere il vettore?:  ");
         scanf_s("%d", &n);
    }while(n &lt 2 || n > 30);
    
    p = (int*)malloc(n*sizeof(int));
    
    for(i = 0; i &lt n; i++)
    {
            printf("Inserisci l'elemento %d di a[%d]= ", i, i);
            scanf_s("%d", (p+i));
    }
    
    // Visualizza il vettore non ancora ordinato
    printf("\nIl vettore non ancora ordinato\n");
    for(i = 0; i &lt n; i++)
    {
        printf("a[%d] = %d  ", i, *(p+i));     
    }
    
    // Richiama la funzione BubbleSort() per ordinare il vettore
    BubbleSort(p, n);
    
    // Visualizza il vettore ordinato
    printf("\n\nIl vettore ordinato:\n");
    for(i = 0; i &lt n; i++)
    {
        printf("a[%d] = %d  ", i, *(p+i));     
    }
    printf("\n\n");
}

Conclusione

Il bubble sort ha diverse varianti, ma il principio rimane lo stesso. La sua complessità è O(n^2). Esistono algoritmi più efficienti, ma il bubbling è sicuramente il più efficace per introdurre il concetto di ordinamento degli elementi di un array.