Bubble sort: differenze tra le versioni

Versione delle 01:40, 16 lug 2025

Versione attuale delle 01:40, 16 lug 2025

Riga 33:

== Spiegazione astratta ==

[[File:Bubble-sort-example-300px.gif|upright=1.6|thumb|Esempio di ''bubble sort'' che ordina gli elementi in senso crescente. Partendo dall'inizio della lista e scorrendola progressivamente, si confrontano due elementi adiacenti e si scambiano le loro posizioni se non sono nel giusto ordine (ossia se il secondo elemento è minore del primo). Dopo la prima [[iterazione]] il massimo si troverà in ultima posizione, quella sua definitiva; dopo la seconda iterazione il secondo massimo si troverà in penultima posizione, anch'essa la sua definitiva; dopo la terza iterazione il terzo massimo si troverà in terz'ultima posizione, anch'essa la sua definitiva e così via. Ad ogni iterazione almeno un elemento si va a collocare nella sua giusta posizione: la procedura termina quando non ci sono più elementi da scambiare. Si noti infine come, per esempio, l'8 sia un ''coniglio'' che si muove velocemente verso destra, mentre il 2 sia una ''tartaruga'' che si muove lentamente verso sinistra.]]

Il bubble sort è un [[algoritmo iterativo]], ossia basato sulla ripetizione di un procedimento fondamentale. La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito (che si scorra l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante; d'ora in poi ipotizzeremo che lo si scorra partendo dall'inizio).

Riga 53:

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

# alla all'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; oltre a portare il numero più grande in fondo, ogni singola iterazione può contribuire anche a un riordinamento parziale degli altri valori. Anche per questo motivo, può accadere (e normalmente accade) che l'array risulti effettivamente ordinato ''prima'' che si sia raggiunta la N-1ª iterazione. Su questa osservazione sono basate le versioni ottimizzate dell'algoritmo.