Bubble sort: differenze tra le versioni

Versione delle 08:54, 11 ott 2021

Versione delle 20:47, 12 dic 2021

Riga 62:

=== Varianti e ottimizzazioni ===

Esistono numerose varianti del bubblesortbubble sort, 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-1ª 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'').