PDA

Visualizza la versione completa : Bubble sort spiegazione


Redix123
16-05-2014, 17:37
A scuola il prof mi ha fatto vedere l'algoritmo di ordinamento bubble sort però non capisco una cosa.



void bubble_sort(int x[], int n)
{
int us, sup, aus;
us = n - 1;
while (us != 0)
{
sup = us;
us = 0;
for (int i = 0; i < sup; i++)
if (x[i]>x[i + 1])
{
aus = x[i];
x[i] = x[i + 1];
x[i + 1] = aus;
us = i;
}
}
}



Ho capito la parte dello scambio tra il valore minore e quello maggiore, ma non riesco a capire a cosa servono le variabile us e sup.
Potreste spiegarmi gentilmente

Scara95
16-05-2014, 17:56
Alla fine del primo ciclo l'array può essere ordinato da 0 a us, ma è sicuramente ordinato da us a n-1 in quanto us conterrà l'indice dell'ultimo scambio avvenuto. Quindi al secondo ciclo puoi fermarti a controllare i valori all'indice contenuto in us. sup serve perché siccome ad ogni ciclo devi cambiare il valore di us ti serve una variabile in cui conservare il precedente valore.

P.s. in realtà tutta quella roba deriva da un'ottimizzazione. Se ti fosse stato spiegato il bubblesort di base e che cosa implica e poi gli vari step di ottimizzazione che derivano da alcune constatazioni non avresti problemi a comprenderlo.

P.p.s. usa i tag code e leggi il regolamento

Redix123
16-05-2014, 19:02
Alla fine del primo ciclo l'array può essere ordinato da 0 a us, ma è sicuramente ordinato da us a n-1 in quanto us conterrà l'indice dell'ultimo scambio avvenuto. Quindi al secondo ciclo puoi fermarti a controllare i valori all'indice contenuto in us. sup serve perché siccome ad ogni ciclo devi cambiare il valore di us ti serve una variabile in cui conservare il precedente valore.

P.s. in realtà tutta quella roba deriva da un'ottimizzazione. Se ti fosse stato spiegato il bubblesort di base e che cosa implica e poi gli vari step di ottimizzazione che derivano da alcune constatazioni non avresti problemi a comprenderlo.

P.p.s. usa i tag code e leggi il regolamento

Grazie mille sei stato utilissimo

Scara95
16-05-2014, 19:06
Prego non c'è di che :ciauz:

Loading