Bubble sort: differenze tra le versioni

Versione delle 10:46, 11 lug 2025

Versione delle 01:39, 16 lug 2025

Riga 38:

Per esempio, saranno confrontati il primo e il secondo elemento, poi il secondo e il terzo, poi il terzo e il quarto e così via fino al confronto fra il penultimo e l'ultimo elemento. Ad ogni confronto, se i due elementi confrontati non sono ordinati secondo il criterio prescelto, vengono scambiati di posizione. Durante ogni iterazione almeno un valore viene spostato rapidamente fino a raggiungere la sua collocazione definitiva; in particolare, alla prima iterazione il numero più grande raggiunge l'ultima posizione dell'array, alla seconda il secondo numero più grande raggiunge la penultima posizione e così via.

Il motivo è semplice e si può illustrare con un esempio. SupponiamoSi supponga che l'array sia inizialmente disposto come segue:

15 6 4 10 11 2

Riga 64:

Esistono numerose varianti del bubble 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 e meno risorse computazionali.

Un insieme di ottimizzazioni si basa sull'osservazione che, se in una data iterazione non avviene alcuno scambio, significa che l'array è sicuramente ordinato, quindi 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 tiene traccia se nell'iterazione corrente si è eseguito almeno uno scambio. La variabile viene impostata a ''false'' all'inizio di ogni iterazione e modificata a ''true'' solo nel caso in cui si proceda a uno scambio. Se al termine di una un'iterazione completa il valore della variabile ''flag'' è rimasto ''false'', ovvero nell'iterazione non sono stati eseguiti scambi, 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 dato dall'assegnamento e dal 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 nessun'iterazione successiva eseguirà scambi in posizioni successive a tale valore ''i''. L'algoritmo può dunque essere ottimizzato memorizzando la posizione a cui avviene l'ultimo scambio durante una un'iterazione e limitando le scansioni dell'array durante le iterazioni successive solo fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo ''overhead'', dato dalla gestione di una variabile aggiuntiva che indica la posizione alla quale la scansione della lista deve fermarsi di volta in volta.

Un'altra variante già menzionata, lo ''shaker sort'', 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 [[Shaker sort|la voce relativa]].

=== Conigli e tartarughe ===

Come detto, la struttura dell'algoritmo porta ad avere elementi che si spostano verso la posizione corretta più velocemente di altri. Tutti gli elementi che si spostano nella stessa direzione di scorrimento dell'indice avanzano più velocemente di quelli che lo fanno in senso contrario. RiprendiamoSi riprende l'esempio precedente. Data la lista

15 6 4 10 11 2

Riga 79:

6 4 10 11 2 15

Qui si osserva il "coniglio" 15 e la "tartaruga" 2: il primo numero, in una sola iterazione, ha attraversato tutta la lista, posizionandosi nella sua collocazione definitiva. Il secondo, invece, durante la stessa iterazione è avanzato di una sola posizione verso la sua collocazione corretta.

Sono stati effettuati diversi tentativi per eliminare le tartarughe e aumentare l'efficienza del Bubble sort: l'algoritmo [[shaker sort]] risolve molto bene questo problema, utilizzando un indice interno la cui direzione di scorrimento è invertita a ogni passaggio; risulta più efficiente del Bubble sort, ma paga un dazio in termini di complessità (<math>O(n^2)</math>). Il [[Comb sort]] compara elementi divisi da una grossa separazione, potendo quindi spostare le tartarughe molto velocemente prima di procedere a controlli fra elementi via via sempre più vicini per rifinire l'ordine della lista (la sua velocità media è comparabile a quella di algoritmi molto più veloci quali il [[quicksort]]).

Riga 108:

=== Ottimizzazioni ===

Le prestazioni del bubble sort possono essere leggermente migliorate tenendo conto del fatto che dopo la prima iterazione l'elemento più grande si troverà certamente nell'ultima posizione della lista, quella sua definitiva; alla seconda iterazione il secondo più grande si troverà in penultima posizione, quella sua definitiva, e così via. Ad ogni iterazione il ciclo dei confronti può accorciarsi di un passo rispetto al precedente, evitando di scorrere ogni volta tutta la lista fino in fondo: all'n-esima iterazione si può quindi fare a meno di trattare gli ultimi n-1 elementi che ormai si trovano nella loro posizione definitiva. PossiamoSi può rappresentare quanto detto con questo secondo pseudocodice:

'''procedure''' BubbleSort(A:lista di elementi da ordinare)

scambio ← true

n ← length'''(A)''' - 2 //poichèpoiché l'indice parte da 0 e devo fermarmi al penultimo elemento del vettore devo togliere 2

'''while''' (scambio) '''do'''

scambio ← false

Riga 121:

n ← n-1 //ad ogni passaggio il ciclo for si accorcia di un'iterazione

Un altro tipo di ottimizzazione deriva dall'osservazione che spesso, alla fine di una un'iterazione, non uno bensì due o più elementi si trovano nella loro posizione definitiva: tutti gli elementi che si trovano a valle dell'ultimo scambio effettuato risultano ordinati e si può evitare di trattarli ancora nell'iterazione successiva.

PossiamoSi può rappresentare quanto detto con questo terzo pseudocodice:

'''procedure''' BubbleSort(A:lista di elementi da ordinare)