Bubble sort: differenze tra le versioni

Versione delle 10:13, 18 nov 2023

Versione delle 15:27, 7 dic 2023

Riga 68:

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).

Un'altra variante già menzionata (lo ''shakersort'') consente di ridurre la probabilità che si verifichi la situazione di [[analisi del caso peggiore|caso peggiore]] (in cui tutte le ottimizzazioni precedentemente citate falliscono e quindi contribuiscono solo negativamente con i relativi ''overhead''); vedi [[shakersortShaker sort|la voce relativa]].

=== Conigli e tartarughe ===