Un'altra considerevole differenza tra i due è che l'ordinamento di bolle è un algoritmo stabile mentre l'ordinamento di selezione è un algoritmo instabile. Un algoritmo è considerato stabile per gli elementi con la stessa chiave che si verificano nello stesso ordine in cui si stavano verificando prima dell'ordinamento nella lista o nell'array. In generale, gli algoritmi più stabili e veloci utilizzano memoria aggiuntiva.
Grafico comparativo
| Base per il confronto | Bubble sort | Selezione sort |
|---|---|---|
| Di base | L'elemento adiacente viene confrontato e scambiato | L'elemento più grande è selezionato e scambiato con l'ultimo elemento (in caso di ordine crescente). |
| La migliore complessità del caso | Sopra) | O (n 2 ) |
| Efficienza | Inefficiente | Migliore efficienza rispetto al bubble sort |
| Stabile | sì | No |
| Metodo | Scambio | Selezione |
| Velocità | Lento | Veloce rispetto al Bubble sort |
Definizione di Bubble Sort
Bubble sort è il più semplice algoritmo iterativo che opera confrontando ogni elemento o elemento con l'elemento accanto ad esso e scambiandoli se necessario. In parole semplici, confronta il primo e il secondo elemento della lista e lo scambia a meno che non siano fuori dall'ordine specifico. Allo stesso modo, il secondo e il terzo elemento vengono confrontati e scambiati, e questo confronto e scambio proseguono fino alla fine dell'elenco. Il numero di confronti nella prima iterazione è n-1, dove n è il numero di elementi in una matrice. L'elemento più grande sarebbe all'ennesimo posto dopo la prima iterazione. E dopo ogni iterazione, il numero di confronti diminuisce e alla fine l'iterazione avviene solo un confronto.
Questo algoritmo è l'algoritmo di ordinamento più lento. La complessità del caso migliore (quando l'elenco è in ordine) dell'ordinamento Bubble è di ordine n ( O (n) ) e la complessità del caso peggiore è O (n2) . Nel migliore dei casi, è di ordine n perché confronta solo gli elementi e non li scambia. Questa tecnica richiede anche spazio aggiuntivo per memorizzare la variabile temporanea.
Definizione di selezione Ordina
L'ordinamento di selezione ha ottenuto prestazioni leggermente migliori ed è efficiente rispetto all'algoritmo di ordinamento a bolle. Supponiamo di voler disporre una matrice in ordine ascendente, quindi funziona trovando l'elemento più grande e scambiandolo con l'ultimo elemento e ripetendo il seguente processo sugli array secondari finché l'intera lista non viene ordinata.
Differenze chiave tra ordinamento a bolle e ordinamento di selezione
- Nel bubble sort, ogni elemento e il suo elemento adiacente vengono confrontati e scambiati se necessario. D'altra parte, l'ordinamento della selezione funziona selezionando l'elemento e scambiando quel particolare elemento con l'ultimo elemento. L'elemento selezionato potrebbe essere il più grande o il più piccolo a seconda dell'ordine, cioè ascendente o discendente.
- La complessità del caso peggiore è la stessa in entrambi gli algoritmi, ad esempio, O (n2), ma la complessità migliore è diversa. L'ordinamento a bolle richiede un ordine di tempo mentre l'ordinamento per selezione consuma un ordine di tempo n.
- Bubble sort è un algoritmo stabile, al contrario, la selezione sort è instabile.
- L'algoritmo di ordinamento delle selezioni è veloce ed efficiente rispetto al bubble sort che è molto lento e inefficiente.
Conclusione
L'algoritmo di ordinamento a bolle viene considerato come l'algoritmo più semplice e inefficiente, ma l'algoritmo di ordinamento di selezione è efficiente rispetto all'ordinamento a bolle. Bubble sort consuma anche ulteriore spazio per la memorizzazione di variabili temporanee e necessita di più swap.
