Arkan ha scritto:
il mio prof insiste molto su bubble sort..io lo so a memoria..però non me ne faccio niente se non capisco come funziona e in quali occasioni va uitlizzato e come va utilizzato..
Il bubble sort mi sembra spiegato abbastanza chiaramente su
wikipedia. Io lo trovo tanmente semplice in sè, che non riesco a trovare un modo più semplice per spiegarlo.
A meno che il problema non stia in come implementarlo, ma nel dimostrare che è corretto.
Esso consiste nello scorrere tutto il vettore più volte, confrontando ogni elemento con il successivo, e scambiandoli di posto se il secondo è più grande del primo. L'ultima scansione della sequenza è quella in cui non si fa nessuno spostamento. Per riprendere l'esempio di prima, partendo da:
10, 20 , 15, 7, 12, 18, 25, 2, 22, 19
1 e 2 due sono in ordine (10,20),
2 e 3 vanno scmabiati (20,15)
10, 15, 20, 7, 12, 18, 25, 2, 22, 19
3 e 4 (del nuovo vettore) vanno scambiati (20,7) -> (7,20)
10, 15, 7, 20, 12, 18, 25, 2, 22, 19
4 e 5 vanno scambiati (20,12) -> (12,20)
10, 15, 7, 12, 20, 18, 25, 2, 22, 19
5 e 6 vanno scambiati (20,18) -> (18,20)
10, 15, 7, 12, 18, 20, 25, 2, 22, 19
6 e 7 sono in ordine (20,25)
7 e 8 vanno scambiati (25,2) -> (2,25)
10, 15, 7, 12, 18, 20, 2, 25, 22, 19
8 e 9 vanno scambiati (25,22) -> (22,25)
10, 15, 7, 12, 18, 20, 2, 22, 25, 19
9 e 10 vanno scambiati (25,19) -> (19,25)
10, 15, 7, 12, 18, 20, 2, 22, 19, 25
A questo punto si riparte dall'inizio del vettore.
1 e 2 sono a posto (10,15)
2 e 3 vanno scambiati (15,7 -> (7,15)
10, 7, 15, 12, 18, 20, 2, 22, 19, 25
3 e 4 ....
Michele