Bubble sort: differenze tra le versioni

Versione delle 18:05, 21 lug 2005

Versione delle 18:06, 21 lug 2005

Riga 21:

# 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 dei valori alle posizioni 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 (vedi sotto).

L'algoritmo comincia con un ciclo in cui ogni elemento, a partire dall'ultimo, è confrontato con l'elemento che lo precede; se i due elementi non si trovano nell'ordine esatto vengono scambiati. Alla fine del primo ciclo inevitabilmente l'elemento 'più leggero' come una bolla sarà risalito in prima posizione. Il secondo ciclo esegue le stesse operazioni escudendo il primo elemento e così facendo risalire il secondo elemento 'più leggero' e così si prosegue fino all'orinamento completo. Se N è la lunghezza del array, occorreranno N-1 di questi cicli.

==Implementazioni==