[C++] BubbleSort e ciclo for interno

[stestisa]

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]

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ù:

[stestisa]

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]

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]

Gentilissimi tutti.

Grazie per avermi fatto chiarezza.

Buona giornata!

Stefano