Ordinamento bolla vs Ordinamento selezione
Bubble sort è un algoritmo di ordinamento che opera scorrendo l'elenco da ordinare ripetutamente mentre si confrontano coppie di elementi adiacenti. Se una coppia di elementi è nell'ordine sbagliato, vengono scambiati per posizionarli nell'ordine corretto. Questa traversata viene ripetuta fino a quando non sono necessari ulteriori scambi. L'ordinamento per selezione è anche un algoritmo di ordinamento, che inizia trovando l'elemento minimo nell'elenco e scambiandolo con il primo elemento. Questo processo viene ripetuto per il resto dell'elenco mettendo in ordine gli elementi scambiati.
Cos'è l'ordinamento a bolle?
Bubble sort è un algoritmo di ordinamento che opera scorrendo l'elenco da ordinare ripetutamente mentre si confrontano coppie di elementi adiacenti. Se una coppia di elementi è nell'ordine sbagliato, vengono scambiati per posizionarli nell'ordine corretto. Questo attraversamento viene ripetuto fino a quando non sono necessari ulteriori scambi (il che significa che l'elenco è ordinato). Poiché gli elementi più piccoli nell'elenco vengono in cima quando una bolla viene in superficie, gli viene assegnato il nome di ordinamento a bolle. L'ordinamento a bolle è un algoritmo di ordinamento molto semplice ma ha una complessità caso-temporale media di O(n2) quando si ordina un elenco con n elementi. Per questo motivo, l'ordinamento a bolle non è adatto per l'ordinamento di elenchi con un numero elevato di elementi. Ma per la sua semplicità, il bubble sort viene insegnato durante le introduzioni agli algoritmi.
Cos'è l'ordinamento di selezione?
Selection sort è anche un altro algoritmo di ordinamento che inizia trovando l'elemento minimo nell'elenco e scambiandolo con il primo elemento. Quindi l'elemento minimo viene trovato dal resto dell'elenco (dal secondo elemento fino all'ultimo elemento nell'elenco) e scambiato con il secondo elemento. Questo processo viene ripetuto per il resto dell'elenco mettendo in ordine gli elementi scambiati. Quindi, nell'ordinamento per selezione, in qualsiasi fase dell'algoritmo, l'elenco è diviso in due parti in cui una parte contiene elementi ordinati e l' altra parte contiene elementi non ordinati. Man mano che l'algoritmo procede, l'elenco ordinato cresce da sinistra a destra. L'ordinamento della selezione ha anche una complessità temporale media di O(n2). Pertanto non è adatto nemmeno per l'ordinamento di elenchi di grandi dimensioni.
Qual è la differenza tra Ordinamento a bolle e Ordinamento a selezione?
Anche se entrambi gli algoritmi di ordinamento a bolle e di ordinamento a selezione hanno una complessità media dei casi di O(n2), l'ordinamento a bolle è quasi sempre superato dall'ordinamento di selezione. Ciò è dovuto al numero di scambi necessari ai due algoritmi (l'ordinamento delle bolle richiede più scambi). Ma a causa della semplicità del bubble sort, la sua dimensione del codice è molto piccola. La stabilità è un' altra differenza in questi due algoritmi. Un algoritmo di ordinamento stabile è un algoritmo di ordinamento che mantiene l'ordine dei record se l'elenco contiene elementi con un valore uguale. In questo senso, il selection sort non è un algoritmo stabile mentre il bubble sort è un algoritmo stabile.
