Bubble sort: differenze tra le versioni

Versione delle 19:01, 9 apr 2021

Versione delle 19:19, 21 lug 2021

Riga 55:

# 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, 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-1esima1ª iterazione. Su questa osservazione sono basate le versioni ottimizzate dell'algoritmo.

=== Analisi dell'algoritmo ===

Riga 64:

Esistono numerose varianti del bubblesort, molte delle quali possono essere definite ottimizzazioni, in quanto mirano a ottenere lo stesso risultato finale (l'ordinamento dell'array) eseguendo, in media, meno operazioni, quindi impiegando meno tempo.

Un insieme di ottimizzazioni si basa sull'osservazione che se, in una data iterazione, non avviene più alcuno scambio, l'array è necessariamente ordinato e l'algoritmo può essere terminato anticipatamente (ovvero senza giungere alla N-1esima1ª iterazione). Una tecnica di ottimizzazione può dunque essere applicata usando una variabile [[logica booleana|booleana]] (o equivalente) usata come "''[[flag]]''" che indica se nell'iterazione corrente si è eseguito almeno uno scambio. La variabile viene reimpostata a ''false'' all'inizio di ogni iterazione, e impostata a ''true'' solo nel caso in cui si proceda a uno scambio. Se al termine di una iterazione completa il valore della variabile ''flag'' è ''false'', l'array è ordinato e l'intero algoritmo viene terminato. Questa tecnica produce una riduzione del tempo ''medio'' di esecuzione dell'algoritmo, pur con un certo [[overhead]] costante (assegnamento e confronto della variabile ''flag'').

Una seconda linea di ottimizzazione (che può essere combinata con la prima) è basata sull'osservazione che (sempre assumendo una scansione dell'array, per esempio, in avanti, e ordinamento crescente) se una data iterazione non sposta nessun elemento di posizione maggiore di un dato valore ''i'', allora si può facilmente dimostrare che nessuna iterazione successiva eseguirà scambi in posizioni successive a tale valore ''i''. L'algoritmo può dunque essere ottimizzato memorizzando l'indice a cui avviene l'ultimo scambio durante una iterazione, e limitando le iterazioni successive alla scansione dell'array solo fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo ''overhead'' (gestione della variabile aggiuntiva che indica la posizione di ultima modifica).