Home
Forum
Inserisci
    
Home
Home
Forum
Inserisci
  
 
_______________________________________________________________________________________________________________________________________________________________________
 
 
  Inserisci un tutorial  
  Totale contenuti: 114
   
 
Sito3D.com Ultimi 15 Tutorial Tutorial
 
   
   
   
   
   
   
   
   
   
   
   
   
   
     
 
Sito3D.com Ultimi 15 Tutorial Template
 
   
   
     
 
Sito3D.com Ultimi 15 Tutorial Guide
 
   
   
   
   
     
 
Sito3D.com Ultimi 15 Tutorial Corsi
 
   
     
 
Contenuti sponsorizzati
 
 
 
  
     
     
 
 
Siete qui: Home > Tutorials > C/C++ > Algoritmi > Bubble Sort
  
     
 
C/C++: Algoritmi: Bubble Sort
  
     
 
Categoria:
  

C/C++
Aggiunto:
  
08/10/2007
Anteprima:
  
No
Download:
  
 
 
 
Le due operazioni piu frequenti fatto sui dati salvati su un computer sono quelli di ordinare degli elementi o di cercare un elemento in una collezione di elementi.
In questo tutorial tratteremmo l'algoritmo di Bubble Sort.
 
Bubble Sort e' una tecnica di ordinamento molto semplice nella quale mettiamo gli elementi di una lista in modo tale da formare coppie adiacenti.
Questo significa che una coppia qualunque è formata dall'elemento [i] e [i+1].
Se l'ordinamento vienne fatto in modo crescente noi dobbiamo scambiare di posto gli elementi della coppia se il primo elemento e' più grande del secondo.

In questo modo per ogni coppia

(list[i],list[i+1]) for
i:=1 to (n1)
if list[i]>list[i+1],

dobbiamo cambiare il posto ai nostri due elementi.
Si ha che gli elementi più grandi saranno sempre più a destra possibile. Facciamo questo processo con i (n1) elementi della lista, che ci darà il valore più grande della lista.
Ripetiamo il processo con le (n2) coppie rimanenti,questo procedimento si fa finché non si arriva ad una sola coppia di elementi.
 
Implementiamo questo algoritmo in C:
 
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
Questa funzione realizza lo scambio di posto tra due elementi. Prende come input due puntatori.
 
void bsort(int list[], int n)
{
int i,j;
for(i=0;i<(n1);
i++)
for(j=0;j<(n(
i+1));j++)
if(list[j] > list[j+1])
swap(&list[j],&list[j+1]);
}
la funzione bsort(int list[],int n) realizza l'algoritmo di bubble sort, prende in ingresso una lista (in questo caso un array
di interi) e la sua lungezza ed ordina gli elementi secondo l'algoritmo sopra enunciato.
 
 

Analizando l'algoritmo si vede che bubble sort è poco efficente,infatti per completare l'ordinamento di una lista ha bisogno di

(n1)+(n2)+(n3)+....+1=n*(n1)/2.

Quindi questo e' un algoritmo di ordine O(n2) .
 
bubble_sort.c

#include <stdio.h>
#define MAX 10 //numero massimo di elementi in un array
/*****************************************************************
*la funzione swap realizza lo scambio dei elementi****
*****************************************************************/
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
/****************************************************************
** bsort e' la funzione che realizza l'algoritmo *********
** di ordinamento, la funzione viene realizzata *******
** con due loop for che ordinano tute le coppie ******
** della lista dato in input ********************************/
void bsort(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]);
}
/***************************************************************
** la funzione readList legge dalla tastiera(stdin) *****
** un array di lungezza n**********************************/
void readlist(int list[],int n)
{
int i;
printf("Inserire gli elementi\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]); //funzione per prendere dall stdin dei charatteri
}
/***************************************************************
** la funzione printlist, data un array di lungezza n ***
** lo stampa in stdout *************************************/
void printlist(int list[],int n)
{
int i;
printf("Gli elementi della lista sono: \n");
for(i=0;i<n;i++){
printf("%d\t",list[i]);
}
printf("\n");
}

int main()
{
int list[MAX], n;
printf("Inserire il numero degli elementi nella lista max = 10\n");
scanf("%d",&n);
readlist(list,n);
printf("La lista prima di ordinarla.\n");
printlist(list,n);
bsort(list,n);
printf("La lista dopo averlo ordinato.\n");
printlist(list,n);

return 0;
}