Bubble sort (Italiano)
Un esempio di bubble sort. Partendo dallinizio della lista, confronta tutte le coppie adiacenti, scambia la loro posizione se non sono nellordine giusto (questultima è più piccola della prima). Dopo ogni iterazione, è necessario un elemento in meno (lultimo) da confrontare finché non ci sono più elementi da confrontare.
PerformanceEdit
Bubble sort ha un caso peggiore e una complessità media di О (n2), dove n è il numero di elementi da ordinare. La maggior parte degli algoritmi di ordinamento pratici hanno una complessità nel caso peggiore o media sostanzialmente migliore, spesso O (n log n). Anche altri algoritmi di ordinamento О (n2), come lordinamento per inserzione, generalmente vengono eseguiti più velocemente del Bubble sort e non sono più complessi. Pertanto, il bubble sort non è un pratico algoritmo di ordinamento.
Lunico vantaggio significativo che il bubble sort ha sulla maggior parte degli altri algoritmi, anche quicksort, ma non per insertion sort, è che la capacità di rilevare che lelenco è ordinato in modo efficiente è integrato nellalgoritmo. Quando lelenco è già ordinato (nel migliore dei casi), la complessità dellordinamento a bolle è solo O (n). Al contrario, la maggior parte degli altri algoritmi, anche quelli con una migliore complessità del caso medio, eseguono lintero processo di ordinamento sul set e quindi sono più complessi. Tuttavia, non solo lordinamento per inserzione condivide questo vantaggio, ma offre anche prestazioni migliori su un elenco sostanzialmente ordinato (con un piccolo numero di inversioni). Inoltre, se si desidera questo comportamento, può essere banalmente aggiunto a qualsiasi altro algoritmo controllando lelenco prima che lalgoritmo venga eseguito.
Il Bubble sort dovrebbe essere evitato nel caso di grandi raccolte. Non sarà efficiente nel caso di una raccolta con ordine inverso.
Rabbits and TurtlesEdit
La distanza e la direzione in cui gli elementi devono spostarsi durante lordinamento determinano le prestazioni del bubble sort perché gli elementi si muovono in direzioni diverse a velocità diverse. Un elemento che deve spostarsi verso la fine dellelenco può spostarsi rapidamente perché può prendere parte a scambi successivi. Ad esempio, lelemento più grande nellelenco vincerà ogni scambio, quindi si sposta in la sua posizione ordinata al primo passaggio anche se inizia vicino allinizio. Daltra parte, un elemento che deve spostarsi verso linizio della lista non può spostarsi più velocemente di un passo per passata, quindi gli elementi si muovono verso linizio molto lentamente. Se lelemento più piccolo si trova alla fine della lista, ci vorranno n − 1 passaggi per spostarlo allinizio. Ciò ha portato questi tipi di elementi a essere chiamati rispettivamente conigli e tartarughe, dopo i personaggi della favola di Esopo La tartaruga e la lepre.
Varie sono stati compiuti sforzi per eliminare le tartarughe per migliorare la velocità del bubble sort. Il cocktail sort è un bubble sort bidirezionale che va dallinizio alla fine e poi si inverte, andando dalla fine allinizio. Può muovere le tartarughe abbastanza bene, ma conserva O (n2) complessità nel caso peggiore. Lordinamento a pettine confronta gli elementi separati da grandi spazi e può spostare le tartarughe molto rapidamente prima di procedere a spazi sempre più piccoli per appianare lelenco. La sua velocità media è paragonabile ad algoritmi più veloci come quicksort.
Esempio passo passoModifica
Prendi un array di numeri “5 1 4 2 8” e ordina larray dal più basso numero al numero maggiore utilizzando lordinamento a bolle. In ogni fase vengono confrontati gli elementi scritti in grassetto. Saranno necessari tre passaggi;
Primo passaggio (5 1 4 2 8) → (1 5 4 2 8), Qui lalgoritmo confronta i primi due elementi e scambia a partire da 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Scambia da 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Scambia da 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), ora, poiché questi elementi sono già in ordine (8 > 5), lalgoritmo non li scambia. Secondo passaggio (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Scambia da 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)
Ora, larray è già ordinato, ma lalgoritmo non sa se è stato completato . Lalgoritmo necessita di un intero passaggio senza alcuno scambio per sapere di essere ordinato.