Perché lordinamento della selezione è più veloce dellordinamento a bolle?

Tutte le complessità che hai fornito sono vere, comunque sono date nella notazione O grande , quindi tutti i valori e le costanti additivi vengono omessi.

Per rispondere alla tua domanda abbiamo bisogno d concentrarsi su unanalisi dettagliata di questi due algoritmi. Questa analisi può essere fatta a mano o trovata in molti libri. Userò i risultati di Knuth “s Art of Computer Programming .

Numero medio di confronti:

• Bubble sort : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Ordinamento di inserzione : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Ordinamento selezione : $ (N + 1) H_N – 2N $

Ora, se tracci quelle funzioni ottieni qualcosa del genere:

Come puoi vedere, lordinamento a bolle è molto peggio allaumentare del numero di elementi, anche se entrambi i metodi di ordinamento hanno lo stesso asintotico complessità.

Questa analisi si basa sul presupposto che linput sia casuale, il che potrebbe non essere sempre vero. Tuttavia, prima di iniziare lordinamento, possiamo permutare in modo casuale la sequenza di input (utilizzando qualsiasi metodo) per ottenere il caso medio.

Ho omesso lanalisi della complessità temporale perché dipende dallimplementazione, ma è possibile utilizzare metodi simili.

Commenti

• Ho un problema con ” possiamo permutare casualmente la sequenza di input per ottenere un caso medio “. Perché può essere fatto più velocemente del tempo richiesto per ordinare?
• Puoi permutare qualsiasi sequenza di numeri che richiederà $ N $ tempo dove $ N $ è la lunghezza della sequenza. È ‘ ovvio che qualsiasi algoritmo di ordinamento basato sul confronto deve avere almeno $ \ mathcal O (N \ log N) $ complessità, quindi anche se aggiungi $ N $ ad esso ‘ La complessità ‘ non verrà modificata così tanto. Comunque stiamo parlando di confronto non di tempo, la complessità del tempo dipende dallimplementazione e dalla macchina in esecuzione, come ho detto nella risposta.
• Immagino che fossi assonnato, hai ragione, la sequenza può essere permutata in tempo lineare .
• Poiché $ H_N = \ Theta (log N) $, il limite di confronto è corretto per lordinamento della selezione? Sembra che ‘ stia sottintendendo che esegue in media O (n log n) confronti.
• Gamma = 0.577216 è Euler-Mascheroni ‘ costante. Il capitolo pertinente è ” Larte della programmazione ” vol 3 sezione 5.2.2 pg. 109 e 129. Come avete tracciato il caso di Bubble Sort esattamente, specialmente il termine O (sqrt (N))? Lhai semplicemente trascurato?

Il costo asintotico, o $ \ mathcal O $ -notazione, descrive il comportamento limitante di una funzione poiché il suo argomento tende allinfinito, ovvero il suo tasso di crescita.

La funzione stessa, ad es. il numero di confronti e / o swap può essere diverso per due algoritmi con lo stesso costo asintotico, a condizione che crescano con lo stesso tasso.

Più specificamente, Bubble sort richiede, in media, $ n / 4 $ swap per voce (ogni voce viene spostata per elemento dalla sua posizione iniziale alla sua posizione finale, e ogni scambio coinvolge due voci), mentre lordinamento per selezione richiede solo $ 1 $ (una volta che il minimo / massimo è stato trovato, viene scambiato una volta alla fine dellarray).

In termini di numero di confronti, Bubble sort richiede $ k \ volte n $ confronti, dove $ k $ è la distanza massima tra la posizione iniziale di una voce e la sua posizione finale, che di solito è maggiore di $ n / 2 $ per valori iniziali distribuiti uniformemente, lordinamento per selezione, tuttavia, richiede sempre confronti $ (n-1) \ times (n-2) / 2 $.

In sintesi, il limite asintotico ti dà una buona idea di come crescono i costi di un algoritmo rispetto alla dimensione dellinput, ma non dice nulla sulle prestazioni relative di diversi algoritmi allinterno dello stesso insieme.

Commenti

• questa è anche unottima risposta
• quale libro preferisci?
• @GrijeshChauhan: I libri sono una questione di gusti, quindi prendi qualsiasi raccomandazione con le pinze. Personalmente mi piacciono Cormen, Leiserson e Rivest ‘ s ” Introduzione agli algoritmi “, che offre una buona panoramica su una serie di argomenti e Knuth ‘ s ” The Art of Computer Programming ” serie se hai bisogno di più / tutti i dettagli su un argomento specifico. Potresti controllare se la domanda sui libri è stata posta qui in precedenza o pubblicare la domanda se non è ‘ t.
• Per me, terzo paragrafo la tua risposta è la risposta effettiva. Non i grafici per input di grandi dimensioni, forniti in unaltra risposta.

Lordinamento a bolle utilizza più tempi di scambio, mentre lordinamento di selezione lo evita.

Quando si utilizza la selezione dellordinamento, al massimo vengono scambiati n volte. ma quando si utilizza il Bubble Sort, si scambia quasi n*(n-1). E ovviamente il tempo di lettura è inferiore al tempo di scrittura anche in memoria. Il tempo di confronto e altri tempi di esecuzione possono essere ignorati. Quindi i tempi di scambio sono il collo di bottiglia critico del problema.

Commenti

• Penso che laltra risposta di Bartek sia più ragionevole ma non posso ‘ votare o un commento … A proposito, penso ancora che il tempo di scrittura influenzi maggiormente e spero che possa tenerne conto se lo vede e concorda.
• Non puoi semplicemente ignorare il numero di confronti, poiché ci sono casi duso in cui il tempo speso per confrontare due elementi può superare di gran lunga il tempo impiegato per scambiare due elementi. Considera un elenco collegato di stringhe estremamente lunghe (diciamo 100k caratteri ciascuna). La lettura di ogni stringa richiederebbe molto più tempo rispetto alla riassegnazione del puntatore.
• @IrvinLim Penso che tu abbia ragione, ma potrei dover vedere i dati statistici prima di cambiare idea.