Contenuto

• Tabella di comparazione
• Definizione di Bubble Sort
• Definizione dell'ordinamento per selezione
• Conclusione

L'ordinamento è uno dei compiti principali nei programmi per computer in cui gli elementi di un array sono disposti in un ordine particolare. L'ordinamento semplifica la ricerca. Bubble sort e Selection sort sono gli algoritmi di ordinamento che possono essere differenziati attraverso i metodi che utilizzano per l'ordinamento. L'ordinamento a bolle scambia essenzialmente gli elementi mentre l'ordinamento per selezione esegue l'ordinamento selezionando l'elemento.

Un'altra notevole differenza tra i due è che l'ordinamento a bolle è un algoritmo stabile mentre l'ordinamento per 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 nell'elenco o nella matrice. In genere, gli algoritmi più stabili e veloci utilizzano memoria aggiuntiva.

1. Tabella di comparazione
2. Definizione
3. Differenze chiave
4. Conclusione

Tabella di comparazione

Base per il confronto	Ordinamento delle bolle	Ordinamento di selezione
Di base	L'elemento adiacente viene confrontato e scambiato	L'elemento più grande viene selezionato e scambiato con l'ultimo elemento (in caso di ordine crescente).
Migliore complessità temporale	Su)	Su2)
Efficienza	Inefficiente	Migliore efficienza rispetto all'ordinamento a bolle
Stabile	sì	No
Metodo	Scambio	Selezione
Velocità	Lento	Veloce rispetto all'ordinamento a bolle

Definizione di Bubble Sort

Ordinamento delle bolle è 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 dell'elenco 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 sono n-1 dove n è gli elementi numerici in un array. L'elemento più grande sarebbe all'ennesima posizione dopo la prima iterazione. E dopo ogni iterazione, il numero di confronti diminuisce e alla fine viene eseguito solo un confronto.

Questo algoritmo è l'algoritmo di ordinamento più lento. La migliore complessità del caso (quando l'elenco è in ordine) dell'ordinamento Bubble è dell'ordine n (Su)) e la complessità peggiore è Su²). 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 dell'ordinamento per selezione

Ordinamento di selezione ha ottenuto prestazioni leggermente migliori ed è efficiente rispetto all'algoritmo di ordinamento delle bolle. Supponiamo di voler disporre un array in ordine crescente, quindi funziona trovando l'elemento più grande e scambiandolo con l'ultimo elemento e ripetendo il seguente processo sugli array secondari fino a quando l'intero elenco non viene ordinato.

Nell'ordinamento per selezione, l'array ordinato e non ordinato non fa alcuna differenza e consuma un ordine di n² (Su²)) nella migliore e nella peggiore delle ipotesi. L'ordinamento per selezione è più veloce dell'ordinamento a bolle.

1. Nell'ordinamento a bolle, ogni elemento e il suo elemento adiacente vengono confrontati e scambiati se necessario. D'altra parte, l'ordinamento di selezione funziona selezionando l'elemento e scambiando quel particolare elemento con l'ultimo elemento. L'elemento selezionato potrebbe essere più grande o più piccolo a seconda dell'ordine, ovvero crescente o decrescente.
2. La complessità del caso peggiore è la stessa in entrambi gli algoritmi, ovvero O (n²), ma la migliore complessità è diversa. L'ordinamento a bolle richiede un ordine di n tempo mentre l'ordinamento di selezione consuma un ordine di n² tempo.
3. L'ordinamento a bolle è un algoritmo stabile, al contrario, l'ordinamento di selezione è instabile.
4. L'algoritmo di ordinamento della selezione è rapido ed efficiente rispetto all'ordinamento a bolle che è molto lento e inefficiente.

Conclusione

L'algoritmo di ordinamento a bolle è considerato l'algoritmo più semplice e inefficiente, ma l'algoritmo di ordinamento per selezione è efficiente rispetto all'ordinamento a bolle. L'ordinamento a bolle consuma inoltre spazio aggiuntivo per l'archiviazione di variabili temporanee e richiede più scambi.