Informatica Programmabile
Vuoi reagire a questo messaggio? Crea un account in pochi click o accedi per continuare.
Accedi

Ho dimenticato la password

Ultimi argomenti attivi
» argomento
Bubble Sort EmptyDom Giu 02, 2013 4:30 pm Da ruggiero98

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

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

»  CALCOLO PERCENTUALE IN C
Bubble Sort EmptySab Apr 20, 2013 8:22 pm Da ruggiero98

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

» Ciao a tutti!
Bubble Sort EmptyGio Mar 22, 2012 4:19 am Da cosmos91

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

» PROGRAMMA: BINARY CODE
Bubble Sort EmptyMar Dic 23, 2008 7:28 pm Da Thalionwen

» saluti a tutti
Bubble Sort EmptyMar Dic 23, 2008 7:12 pm Da Thalionwen

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

» un semplice ciao
Bubble Sort EmptySab Nov 29, 2008 11:38 am Da ya89

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

» FORUM: I nuovi banner
Bubble Sort EmptyVen Nov 14, 2008 2:48 pm Da Thalionwen

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

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

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

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

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

» [PC] Sacred 2
Bubble Sort EmptyLun Nov 10, 2008 10:49 pm Da ab89

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

Flusso RSS


Yahoo! 
MSN 
AOL 
Netvibes 
Bloglines 



Bubble Sort

2 partecipanti

Andare in basso

Bubble Sort Empty Bubble Sort

Messaggio Da ab89 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
ab89
ab89
Admin
Admin

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

Scheda personaggio
PF:

Torna in alto Andare in basso

Bubble Sort Empty Re: Bubble Sort

Messaggio Da Eine The Phantom 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
Eine The Phantom
Eine The Phantom
Admin
Admin

Numero di messaggi : 37
Data d'iscrizione : 28.09.08

https://infonprog.forumattivo.it

Torna in alto Andare in basso

Torna in alto

- Argomenti simili

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