PDA

Visualizza la versione completa : [C++] BubbleSort e ciclo for interno


stestisa
16-12-2011, 10:55
Salve a tutti. Mi sono trovato stamattina di fronte a un Bubble Sort di cui non capisco il primo "for". Ciò che non capisco è semplicemente a cosa serve il ciclo for con il k, dato che mi sembra totalmente irrilevante.


void BubbleSort (int v[], int n)
{
for (int k=n-1; k>0; k--)
for (int i=0; i<k; i++)
if (v[i] > v[i+1])
swap(v[i],v[i+1]);
}

Lo schema che ho fatto per provare a capire a cosa serva è il seguente:



v[]={10,4,7,2,1}; n=5;
ciclo for
…k=5->i=0--> se v[0]>v[1] cambia v[0] con v[1]
…k=4->i=1--> se v[1]>v[2] cambia v[1] con v[2]


Qualcuno riesce a chiarirmi le idee?

MItaly
16-12-2011, 11:10
Il for più interno fa "salire" fino in cima il valore più alto nella iterazione corrente delle k. Il for esterno ripete questo gioco (stringendo il set su cui il for interno opera man mano, dato che ad ogni giro viene messo al posto giusto il valore più alto) finché non ci si riduce ad un set di un solo elemento. Credo che un'immagine possa chiarire di più:
http://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif

stestisa
16-12-2011, 11:18
Mai ricevuto risposta più chiara della tua.

Una cosa soltanto:
Se invece di far decrescere il k da n-1 a 1, facessi il contrario? Ovvero da 1 a n-1? Non sarebbe la stessa cosa?

Grazie per la chiarezza.

Stefano

ramy89
16-12-2011, 11:44
Quello che fa è:
- Trascina l' elemento massimo dell' array [0....k] in posizione k;
- Decrementa k.

Quindi se hai l' array {10,4 7,2 1} dopo la prima iterazione del for esterno in v[4] c'è 10, e k viene decrementato perchè non c'è bisogno di riconsiderare l' elemento 4,dato che è il massimo.
Se k partiva da 0 e arrivava fino a n-1 non va bene perchè il ciclo interno verrebbe eseguito prima su un singolo elemento, poi su 2, poi su 3 .... e non avrebbe l' effetto di ordinare completamente l' array,non ne sono sicuro ma penso che alla fine del ciclo avresti {4,2,7,10,1}.
Per farlo funzionare dovresti modificare anche il for interno:


for (int k=1; k<=n-1; k++)
for (int i=n-1; i>=k; i--)
if (v[i] < v[i-1])
swap(v[i],v[i+1]);

Il risultato sarebbe identico, ha cioè l' effetto di ordinare l' array, ma in modo diverso.
Invece di trascinare gli elementi più grandi nelle ultime posizioni del vettore, trascina gli elementi più piccoli nelle posizioni iniziali del vettore.

stestisa
16-12-2011, 11:52
Gentilissimi tutti.

Grazie per avermi fatto chiarezza.

Buona giornata!

Stefano

Loading