Bubble sort

Il bubble sort, ordinamento a bolle, realizza l'ordinamento di una lista di valori eseguendo confronti fra coppie adiacenti. L'esito del confronto stabilisce il valore da spostare, man mano verso il fondo della lista. Se in una iterazione, ancora prima di scorrere tutte le coppie, non avvengono scambi la lista è allora già ordinata! Queste le fasi previste dall'algoritmo:

• inizializzare una variabile per stabilire se durante una iterazione avviene almeno uno scambio fra coppie adiacenti e un indice che punta all'ultimo elemento del vettore ordinato;
• scorrere la lista, confrontando le coppie adiacenti ed effettuando, eventualmente, lo scambio (segnando l'evento nell'apposita variabile) se queste non sono tra loro ordinate;
• ripetere il precedente passaggio arrestando la serie di confronti al valore precedentemente già ordinato e puntato dall'indice (che man mano verrà quindi decrementato);

L'algoritmo, allora, termina quando l'indice che punta l'ultimo elemento ordinato raggiunge la testa della lista oppure, come già detto, se in una iterazione non si verificano scambi. Di seguito propongono una realizzazione dell'algoritmo in linguaggio C:

/* bubblesort */
#include <stdio.h>
#include <stdbool.h>

#define LENGTH 10

void bubbleSort(int *array,int length);
void swap(int *x, int *y);

int main(void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   bubbleSort(array,LENGTH);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
   return 0;
}

void bubbleSort(int *array,int length) {
   int i,temp,step=0;
   bool change;
   do {
      change=false;
      for (i=0;i<length-1-step;i++) {
         if (array[i]>array[i+1]) {
            swap(&array[i],&array[i+1]);
            change=true;
         }
      }
      step++;
   }
   while(change==true);
}

void swap(int *x, int *y) {
   int temp=*x;
   *x=*y;
   *y=temp;
}