Differenza tra ordinamento a bolle e selezione

Bubble Sort vs Selection Sort

Bubble sort è un algoritmo di ordinamento che opera scorrendo l'elenco per essere ordinato ripetutamente durante il confronto di coppie di elementi adiacenti. Se una coppia di elementi è nell'ordine sbagliato, vengono scambiati per inserirli nell'ordine corretto. Questa traversata viene ripetuta finché non sono richiesti ulteriori scambi. L'ordinamento della 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 inserendo gli elementi scambiati in ordine.

Che cos'è Bubble Sort?

Bubble sort è un algoritmo di ordinamento che opera scorrendo l'elenco per essere ordinato ripetutamente durante il confronto di coppie di elementi adiacenti. Se una coppia di elementi è nell'ordine sbagliato, vengono scambiati per inserirli nell'ordine corretto. Questa traversata viene ripetuta finché non sono richiesti ulteriori scambi (il che significa che l'elenco è ordinato). Poiché gli elementi più piccoli nella lista arrivano in cima quando una bolla viene in superficie, viene assegnato il nome bubble sort. Bubble sort è un algoritmo di ordinamento molto semplice ma ha una complessità nel tempo di caso medio di O (n2) quando si ordina una lista con n elementi. A causa di ciò, l'ordinamento di bolle non è adatto per ordinare gli elenchi con un numero elevato di elementi. Ma a causa della sua semplicità, il bubble sort viene insegnato durante le introduzioni agli algoritmi.

Cos'è l'ordinamento di selezione?

L'ordinamento selezione è anche un altro algoritmo di ordinamento che inizia trovando l'elemento minimo nell'elenco e lo scambia con il primo elemento. Quindi l'elemento minimo viene trovato dal resto dell'elenco (dal secondo elemento fino all'ultimo elemento nell'elenco) e sostituito con il secondo elemento. Questo processo viene ripetuto per il resto dell'elenco inserendo gli elementi scambiati in ordine. Quindi, nell'ordinamento di selezione, in qualsiasi fase dell'algoritmo, la lista è divisa in due parti in cui una parte contiene elementi ordinati e l'altra parte contiene elementi non ordinati. Man mano che procede l'algoritmo, la lista ordinata cresce da sinistra a destra. L'ordinamento di selezione ha anche una complessità temporale di caso medio di O (n2). Pertanto, non è adatto per l'ordinamento di elenchi di grandi dimensioni.

Qual è la differenza tra Bubble Sort e Selection Sort?

Anche se sia gli algoritmi di ordinamento a bolle che di ordinamento di selezione hanno complessità di tempo medio di caso di O (n2), l'ordinamento di bolle è quasi tutto il tempo sovraperformato dall'ordinamento di selezione. Ciò è dovuto al numero di swap necessari per i due algoritmi (i tipi di bolle richiedono più swap). Ma a causa della semplicità di 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 conserva l'ordine dei record se l'elenco contiene elementi con un valore uguale. In questo senso, sort sort non è un algoritmo stabile, mentre bubble sort è un algoritmo stabile.