Accedi
Ultimi argomenti attivi
Migliori postatori
ab89 | ||||
Thalionwen | ||||
Eine The Phantom | ||||
Reaulece | ||||
ya89 | ||||
root | ||||
Infernet89 | ||||
Pablomares | ||||
ruggiero98 | ||||
ieschfor |
Bubble Sort
2 partecipanti
Pagina 1 di 1
Bubble Sort
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 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.
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 :
Ecco ora un programmino che lo utilizza
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
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.
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
ab89- Admin
- Numero di messaggi : 74
Età : 35
Località : Rovigo
Data d'iscrizione : 29.09.08
Scheda personaggio
PF:
Re: Bubble Sort
Una buona versione
Ma preferisco di più il quicksort... come dire... è più nelle mie corde
Ma preferisco di più il quicksort... come dire... è più nelle mie corde
Pagina 1 di 1
Permessi in questa sezione del forum:
Non puoi rispondere agli argomenti in questo forum.
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