Accedi

Ho dimenticato la password

Ultimi argomenti
» argomento
Dom Giu 02, 2013 4:30 pm Da ruggiero98

» problema con la funzione SE aiutoooo x favore?????
Dom Giu 02, 2013 4:18 pm Da ruggiero98

» aiuto in programma con if
Dom Mag 26, 2013 5:39 pm Da ruggiero98

»  CALCOLO PERCENTUALE IN C
Sab Apr 20, 2013 8:22 pm Da ruggiero98

» Costruire un temporizzatore software per accensione luci a led
Lun Mar 25, 2013 2:34 pm Da Cristina Shady

» Ciao a tutti!
Gio Mar 22, 2012 4:19 am Da cosmos91

» Virtualbox VS le periferiche USB
Mar Apr 06, 2010 1:49 pm Da dandeciani

» PROGRAMMA: BINARY CODE
Mar Dic 23, 2008 7:28 pm Da Thalionwen

» saluti a tutti
Mar Dic 23, 2008 7:12 pm Da Thalionwen

» GUIDA : CAP 1 LEZIONE 1 Elementi di base dei programmi in C [Prima Parte]
Sab Nov 29, 2008 11:44 am Da ya89

» un semplice ciao
Sab Nov 29, 2008 11:38 am Da ya89

» Aiuto per alice 7 mega
Ven Nov 14, 2008 4:03 pm Da root

» FORUM: I nuovi banner
Ven Nov 14, 2008 2:48 pm Da Thalionwen

» Zooming Ricorsivo, questo sconosciuto.
Ven Nov 14, 2008 2:43 pm Da Thalionwen

» GUIDA : LEZIONE 4 : UTILIZZARE GLI ARRAY IN C#
Ven Nov 14, 2008 1:54 pm Da ab89

» GUIDA : CAP 1 LEZIONE 1 Elementi di base dei programmi in C [Terza e Ultima Parte]
Ven Nov 14, 2008 12:41 am Da ab89

» GUIDA : CAP 1 LEZIONE 1 Elementi di base dei programmi in C [Seconda Parte]
Mer Nov 12, 2008 12:59 am Da ab89

» [PS2] Dark Cloud
Mar Nov 11, 2008 6:50 pm Da ab89

» [PC] Sacred 2
Lun Nov 10, 2008 10:49 pm Da ab89

» GUIDA : CAP 1 LEZIONE 3 INTRODUZIONE AGLI ARRAY
Lun Nov 10, 2008 1:37 pm Da ab89

Flusso RSS


Yahoo! 
MSN 
AOL 
Netvibes 
Bloglines 



Bubble Sort

Andare in basso

Bubble Sort

Messaggio Da ab89 il Lun Ott 06, 2008 11:05 pm

Bubble Sort è un algoritmo di ordinamento. Ne esiste una versione per così dire base, e svariate migliorie.
Non mi soffermo sulla teoria, ma mi concentrerò a spiegarvi a livello pratico il modo con il quale è possibile ordinare degli elementi.

Preso un array di 5 elementi come il seguente :

4,5,2,4,8

Il bubblesort si occupa di spostare in coda al vettore l'elemento più grande se ordinato in modo crescente, altrimenti ci sarà l'elemento più piccolo.
Ora considero il sendo crescente.
Quindi possiamo asserire che se ripetiamo l'operazione 4 volte (Numero Elementi Da ordinare - 1) avremo gli elementi più grandi in coda al vettore e ordinati.
Qualcuno si potrebbe domandare perchè 4 volte se ci sono 5 elementi ? A quei qualcuno rispondo che dato che abbiamo 5 elementi, se gli ultimi 4 sono ordinati il primo elemento del vettore è anche esso ordinato.

Il secondo passo è verificare se si può migliorare l'algoritmo. Ovviamente si.
La miglioria che si può apportare è la seguente.
Ad ogni ripetizione di ordinamento, sappiamo che il numero più grande viene messo in coda.
Quindi il vettore dopo le varie operazioni risulta essere :
1 ) 4 2 4 5 8
2 ) 2 4 4 5 8
3 ) 2 4 4 5 8
4 ) 2 4 4 5 8

L'elemento in grassetto è quello che viene posizionato correttamente ad ogni operazione.
Si può notare che una volta che un elemento è posizionato correttamente esso è il numero più grande, come nel caso di 8. Poi il 5. Poi il 4 e così via.. Quindi è ovvio che risulta inutile alla seconda operazione confrontare il 5 con il 8 in quanto so che l'ultimo elmento è il più grande. Quindi la seconda miglioria è quella di limitare la sezione del vettore da esaminare. Quindi le operazioni vengono semplificate.

N
v[0]
v[1]
v[2]
v[3]
v[4]
ELEMENTI
N CONTROLLI
1
4
2
4
5
8
5
4
2
2
4
4
5
8
4
3
3
2
4
4
5
8
3
2
4
2
4
4
5
8
2
1


In rosso gli elementi che ogni volta vengono sottoposti al confronto. SI può notare che in questo modo il numero totale di controlli è pari a 4 + 3 + 2 + 1 = 10 mentre nell'altro caso erano 4 + 4 + 4 + 4 = 16.

Un'ulteriore miglioria all'algoritmo è la seguente.
Pensate di avere un vettore come quello nell'esempio. Se doveste ordinarlo a mano sicuramente vi fermereste alla seconda operazione, in quanto gli elementi sono già tutti ordinati. In effetti non avebbe senso applicare un'algoritmo di ordinamento ad un vettore già ordinato. E' questa appunto la miglioria finale. Arrestare l'algoritmo quando gli elementi sono già ordinati.

Ecco il metodo bubblesort elaborato :

Codice:

void bubbleSort(int v[], int numElementi)
{
    int i,j;
    int nScambi = 1;
   
    i = 0;
   
    while (nScambi > 0 && i < numElementi - 1){
        nScambi = 0;
        for (j = 0; j < numElementi - i - 1; j++)
            if (v[j] > v[j+1]){
                nScambi++;     
                swapAB(j,j+1,v);
                }
        i++;
        }
}

void swapAB(int x, int y, int v[])
{
    int tmp = v[x];
    v[x] = v[y];
    v[y] = tmp;
}


Ecco ora un programmino che lo utilizza
Codice:

#include <stdio.h>

#define NUMERO_ELEMENTI 5

void bubbleSort(int v[], int N);
void swapAB(int x, int y, int v[]);

int main(int argc, char *argv[])
{
  int v[NUMERO_ELEMENTI];
  int x ;
 
  v[0]=14;
  v[1]=13;
  v[2]=14;
  v[3]=21;
  v[4]=22;
 
  bubbleSort(v,NUMERO_ELEMENTI);
 
  for(x = 0; x < NUMERO_ELEMENTI; x++)
    printf("%d\n",v[x]);
 
  system("PAUSE");   
  return 0;
}

void bubbleSort(int v[], int numElementi)
{
    int i,j;
    int nScambi = 1;
   
    i = 0;
   
    while (nScambi > 0 && i < numElementi - 1){
        nScambi = 0;
        for (j = 0; j < numElementi - i - 1; j++)
            if (v[j] > v[j+1]){
                nScambi++;     
                swapAB(j,j+1,v);
                }
        i++;
        }
}

void swapAB(int x, int y, int v[])
{
    int tmp = v[x];
    v[x] = v[y];
    v[y] = tmp;
}


Tutto quanto scritto è stato frutto di un'analisi personale. In caso di perplessità sono a disposizione. Grazie
Il codice è liberamente utilizzabile purchè se ne citi la fonte Laughing

_________________
生きるためにもあまり変過ぎるし、死ぬためにもあまり珍し過ぎる。

What D.Gray-man Character Are You?
Hosted By theOtaku.com: Animee

avatar
ab89
Admin
Admin

Numero di messaggi : 74
Età : 29
Località : Rovigo
Data d'iscrizione : 29.09.08

Scheda personaggio
PF:

Visualizza il profilo

Torna in alto Andare in basso

Re: Bubble Sort

Messaggio Da Eine The Phantom il Mar Ott 28, 2008 1:57 am

Una buona versione Very Happy

Ma preferisco di più il quicksort... come dire... è più nelle mie corde Very Happy

_________________
avatar
Eine The Phantom
Admin
Admin

Numero di messaggi : 37
Data d'iscrizione : 28.09.08

Visualizza il profilo http://infonprog.forumattivo.it

Torna in alto Andare in basso

Torna in alto


 
Permessi di questa sezione del forum:
Non puoi rispondere agli argomenti in questo forum