Programmando Facile

Algoritmi – Bubble Sort

Il Bubble Sort è un semplice algoritmo di ordinamento. Nel Bubble Sort gli elementi da ordinare formano una lista di coppie adiacenti. Questo serve perché l’algoritmo passa ripetutamente nella lista da ordinare, confrontando due elementi alla volta, scambiandoli se non sono nel giusto ordine.

Il nome Bubble Sort deriva dal fatto che l’algoritmo può essere visto come delle bolle con all’interno gli elementi da ordinare. Man a mano che si procede con l’ordinamento le bolle vanno verso l’alto, o meglio la bolla con l’elemento più piccolo sale verso l’alto seguita dalle altre.

Qui di seguito il codice sorgente del Bubble Sort implementato in C, l’ordinamento viene effettuato su una lista non ordinata di numeri interi.

#include <stdio.h>
#include <stdlib.h> 

void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
void bublesort(int list[], int n)
{
   int i,j;
   for(i=0;i<(n-1);i++)
      for(j=0;j<(n-(i+1));j++)
             if(list[j] > list[j+1])
                    swap(&list[j],&list[j+1]);
}

void printlist(int list[],int n)
{
   int i;
   for(i=0;i<n;i++)
      printf("%d\t",list[i]);
}

void main()
{
   const int MAX_ELEMENTS = 10;
   int list[MAX_ELEMENTS];

   int i = 0;

   // generate random numbers and fill them to the list
   for(i = 0; i < MAX_ELEMENTS; i++ ){
	   list[i] = rand();
   }
   printf("The list before sorting is:\n");
   printlist(list,MAX_ELEMENTS);

   // sort the list
   bublesort(list,MAX_ELEMENTS);

   // print the result
   printf("The list after sorting using bubble sorting algorithm:\n");
   printlist(list,MAX_ELEMENTS);
}