Bubble sort: differenze tra le versioni

Versione delle 18:03, 21 lug 2005

Versione delle 18:05, 21 lug 2005

Riga 19:

# se i numeri sono in tutto N, dopo N-1 iterazioni si avrà la garanzia che l'array sia ordinato;

# alla iterazione i-esima, le ultime i-1 celle dell'array ospitano i loro valori definitivi, per cui la sequenza di confronti può essere terminata col confronto deldei valorevalori dialle posizioneposizioni N-1-i e N-i.

Ovviamente, a ogni iterazione può accadere che più numeri vengano spostati; per cui, oltre a portare il numero più grande in fondo all'array, ogni singola iterazione può contribuire anche a un riordinamento parziale degli altri valori. Anche per questo motivo, può accadere (normalmente accade) che l'array risulti ordinato ''prima'' che si sia raggiunta la N-1esima iterazione. Su questa osservazione sono basate alcune ottimizzazioni dell'algoritmo.