Ordinamento bolla vs Ordinamento inserimento
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 inserimento è anche un algoritmo di ordinamento, che opera inserendo un elemento nell'elenco di input nella posizione corretta in un elenco già ordinato. Questo processo viene applicato ripetutamente fino a quando l'elenco non viene ordinato.
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 per inserimento?
Insertion sort è un altro algoritmo di ordinamento, che opera inserendo un elemento nell'elenco di input nella posizione corretta in un elenco (che è già ordinato). Questo processo viene applicato ripetutamente fino a quando l'elenco non viene ordinato. Nell'ordinamento per inserimento, l'ordinamento viene eseguito sul posto. Pertanto, dopo l'i-esima iterazione dell'algoritmo, le prime voci i+1 nell'elenco verranno ordinate e il resto dell'elenco non verrà ordinato. Ad ogni iterazione, il primo elemento della parte non ordinata dell'elenco verrà preso e inserito nella posizione corretta nella sezione ordinata dell'elenco. L'ordinamento dell'inserzione ha una complessità media del tempo di caso di O(n2). Per questo motivo, anche l'ordinamento per inserimento non è adatto per l'ordinamento di elenchi di grandi dimensioni.
Qual è la differenza tra Bubble Sort e Insertion Sort?
Anche se entrambi gli algoritmi di ordinamento a bolle e di ordinamento per inserimento hanno una complessità media dei casi di O(n2), l'ordinamento a bolle è quasi sempre superato dall'ordinamento per inserimento. 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. Inoltre esiste una variante dell'ordinamento per inserimento chiamato shell sort, che ha una complessità temporale di O(n3/2), che ne consentirebbe l'uso pratico. Inoltre, l'ordinamento per inserimento è molto efficiente per l'ordinamento di elenchi "quasi ordinati", se confrontato con l'ordinamento a bolle.
