Perché è costituto meglio di mergesort?

https://stackoverflow.com/questions/70402

09-06-2019
|

Domanda

Mi è stato chiesto questa domanda durante un'intervista.Sono entrambi O(nlogn) e, tuttavia, la maggior parte delle persone utilizzare Quicksort invece di Mergesort.Perché è che?

Soluzione

Quicksort ha O(n²) nel caso peggiore di runtime e O(nregistron) caso medio di esecuzione.Tuttavia, è superiore a tutto il merge sort in molti scenari, perché molti fattori influenzano un algoritmo di runtime, e, quando li prende tutti insieme, quicksort vince.

In particolare, la spesso citata per tempo di esecuzione di algoritmi di ordinamento si riferisce al numero di confronti o il numero di operazioni di swap necessario eseguire per ordinare i dati.Questo è davvero un buon indicatore di performance, soprattutto perché è indipendente dall'hardware sottostante design.Tuttavia, altre cose – come località di riferimento (ad es.abbiamo letto un sacco di elementi che sono probabilmente in cache?) – svolgere un ruolo importante anche su hardware corrente.Quicksort, in particolare, richiede un po ' di spazio aggiuntivo e possiede una buona cache località, e questo lo rende più veloce il merge sort, in molti casi.

Inoltre, è molto facile per evitare di quicksort il peggiore tempo di esecuzione O(n² quasi interamente tramite un'opportuna scelta del perno quali scegliere a caso (questo è un ottimo gioco di strategia).

In pratica, molte moderne implementazioni di quicksort (in particolare libstdc++’s std::sort) sono in realtà introsort, il cui teorico nel caso peggiore è O(nregistron), come il merge sort.Il servizio consente di limitare la profondità di ricorsione, e il passaggio ad un diverso algoritmo (heapsort) una volta che si supera il logn.

Altri suggerimenti

Come molti hanno notato, il caso medio di prestazioni per il quicksort è più veloce di mergesort. Ma questo è vero solo se si stanno assumendo costante il tempo di accedere a qualsiasi pezzo di memoria su richiesta.

In RAM questa ipotesi non è generalmente troppo male (non è sempre vero, perché di cache, ma non è troppo male).Tuttavia, se i dati della tua struttura è abbastanza grande per vivere su disco, quindi quicksort ottiene ucciso dal fatto che la media del disco, non qualcosa come 200 random cerca per secondo.Ma che lo stesso disco non ha problemi di lettura o scrittura megabyte al secondo di dati in modo sequenziale.Che è esattamente quello che mergesort fa.

Pertanto, se i dati devono essere ordinati su disco, è davvero, davvero vuoi usare qualche variazione sul mergesort.(In genere si quicksort sottoelenchi, quindi avviare la fusione di loro al di sopra di una certa dimensione di soglia.)

Inoltre se avete a che fare nulla con set di dati di dimensioni, riflettere su come evitare che cerca di disco.Per esempio questo è il motivo per cui è normale che i consigli che si trascina indici prima di fare grandi carichi di dati nel database, e quindi ricostruire l'indice più tardi.Il mantenimento dell'indice durante il carico di mezzi costantemente alla ricerca di disco.Per contro, se si elimina gli indici, quindi il database in grado di ricostruire l'indice, prima di smistamento di informazioni per essere affrontati utilizzando un mergesort, ovviamente!) e poi caricarlo in un b-tree datastructure per l'indice.(B-alberi sono mantenute naturalmente in ordine, in modo da poter caricare uno da un set di dati ordinati con pochi cerca di disco).

Ci sono stati un certo numero di occasioni in cui la comprensione di come evitare ricerche su disco mi ha permesso di elaborazione dati posti di lavoro richiedere ore invece di giorni o settimane.

In realtà, QuickSort è O(n²).La sua caso medio il tempo di esecuzione è O(nlog(n)), ma la sua nel caso peggiore è O(n²), che si verifica quando si esegue su una lista che contiene alcuni oggetti unici.Randomizzazione richiede O(n).Naturalmente, questo non cambia la sua peggiore dei casi, impedisce solo un utente malintenzionato per fare il tuo sorta prendere un lungo periodo di tempo.

QuickSort è più popolare perché:

È posto (MergeSort richiede memoria aggiuntiva lineare del numero di elementi da ordinare).
Ha un piccolo nascosto costante.

"eppure la maggior parte delle persone utilizzare Quicksort invece di Mergesort.Perché è che?"

Psicologica motivo che non è stato dato è semplicemente che il Quicksort è più abilmente chiamato.cioè un buon marketing.

Sì, Quicksort con tripla creazione di partizioni è probabilmente uno dei migliori generali scopo algoritmi di ordinamento, ma c'è sempre il fatto che anche il "Rapido" ordinamento suoni molto più potente di "Unione" di sorta.

Come altri hanno notato, nel caso peggiore di Quicksort è O(n^2), mentre mergesort e heapsort soggiorno in O(nlogn).Sul caso medio, tuttavia, tutti e tre sono in O(nlogn);quindi sono per la stragrande maggioranza dei casi comparabili.

Ciò che rende Quicksort meglio, in media, è che il ciclo interno implica il confronto tra alcuni valori con una sola, mentre gli altri due termini sono diversi per ogni confronto.In altre parole, Quicksort non la metà come molti di legge, come gli altri due algoritmi.Sulla Cpu moderne performance è fortemente dominato da tempi di accesso, così, alla fine, Quicksort finisce per essere un grande di prima scelta.

Vorrei aggiungere che dei tre algoritms che è stato detto finora (mergesort, quicksort e heap sort) solo mergesort è stabile.Che è, l'ordine non cambia per quei valori che hanno la stessa chiave.In alcuni casi questo è auspicabile.

Ma, a dire la verità, in pratica la maggior parte delle persone hanno bisogno solo di una buona performance media e quicksort è...veloce =)

Tutti i tipi di algoritmi hanno i loro alti e bassi.Vedere Articolo di Wikipedia per algoritmi di ordinamento per una buona visione.

Da la voce di Wikipedia su Quicksort:

Quicksort compete anche con mergesort, un altro ordinamento ricorsivo algoritmo ma con il vantaggio di nel caso peggiore Θ(nlogn) tempo di esecuzione.Mergesort è uno stabile ordinamento, a differenza di quicksort e heapsort, e può essere facilmente adattato per funzionare su collegati liste ed elenchi memorizzati sul lento-per-accedere a contenuti multimediali come disco di archiviazione o di archiviazione collegata alla rete.Anche se quicksort può essere scritto operare su di liste collegate, spesso soffrono di problemi di articolazione delle scelte senza l'accesso casuale.Il principale svantaggio di mergesort è che, durante il funzionamento su array, richiede Θ(n) ausiliario lo spazio nel migliore dei casi, mentre il variante di quicksort con posto partizionamento e ricorsività usa solo Θ(logn) spazio.(Si noti che, quando operando su liste collegate, mergesort richiede solo una piccola quantità costante ausiliari di archiviazione.)

Mu! Quicksort non è meglio, è adatto anche per un diverso tipo di applicazione, di mergesort.

Mergesort è la pena di considerare se la velocità è l'essenza, le cattive prestazioni nel caso peggiore, non può essere tollerata, e lo spazio extra è disponibile.1

Si afferma che essi «Sono entrambi O(nlogn) [...]».Questo è sbagliato.«Quicksort utilizza circa n^2/2 confronti nel caso peggiore.»1.

Tuttavia la proprietà più importante secondo la mia esperienza, è la facile implementazione di accesso sequenziale è possibile utilizzare durante l'ordinamento quando si utilizza linguaggi di programmazione, con l'imperativo paradigma.

1 Sedgewick, Algoritmi

Quicksort è il più veloce algoritmo di ordinamento in pratica, ma ha un certo numero di casi di patologie che possono fare è eseguire male come O(n2).

Heapsort è garantito per l'esecuzione O(n*ln(n)) e richiede solo finito di archiviazione aggiuntivo.Ma ci sono molte citazioni di reali prove che dimostrano che heapsort è significativamente più lento di quicksort in media.

Wikipedia la spiegazione è:

In genere, quicksort è significativamente più veloce, in pratica, di altri Θ(nlogn) algoritmi, perché il suo ciclo interno può essere efficacemente attuato sulla maggior parte delle architetture, e in più i dati del mondo reale è possibile fare le scelte progettuali che minimizzano la probabilità di richiedere quadratica tempo.

Quicksort

Mergesort

Penso che ci sono anche problemi con la quantità di storage necessaria per Mergesort (che è Ω(n)) che quicksort implementazioni non hanno.Nel peggiore dei casi, essi sono la stessa quantità di algoritmica tempo, ma mergesort richiede più spazio di archiviazione.

Quicksort NON è migliore di mergesort.Con O(n^2) (caso peggiore che accade raramente), quicksort è potenzialmente molto più lento rispetto a O(nlogn) del merge sort.Quicksort ha meno overhead, quindi, con piccoli n e i computer lenti, è meglio.Ma i computer sono oggi così in fretta che l'overhead aggiuntivo di un mergesort è trascurabile e il rischio di una lenta quicksort supera di gran lunga l'insignificante overhead di mergesort nella maggior parte dei casi.

Inoltre, un mergesort foglie di elementi con chiavi identiche nel loro ordine originale, un elemento utile.

Vorrei aggiungere all'esistente grandi risposte un po 'di calcoli su come QuickSort esegue quando divergenti dal caso migliore e come probabile che sia, e spero di aiutare la gente a capire un po' meglio perché la O(n^2) il caso non è di reale interesse più sofisticati, implementazioni di QuickSort.

Al di fuori di random access problemi, ci sono due fattori principali che possono influenzare le prestazioni di QuickSort e sono entrambi legati a come il pivot confronta i dati ordinati.

1) Un piccolo numero di tasti nei dati.Un set di dati di tutti, lo stesso valore di ordinamento in n^2 volta su una vaniglia 2-partizione di QuickSort, perché tutti i valori tranne il perno in posizione, sono collocati su un lato di ogni tempo.Moderne implementazioni indirizzo di questa con metodi come l'utilizzo di un 3-partizione di sorta.Questi metodi eseguire su un set di dati di tutte lo stesso valore nel tempo O(n).Quindi, utilizzando un'implementazione significa che un ingresso con un piccolo numero di tasti in realtà migliora le prestazioni in tempo e non è più una preoccupazione.

2) Molto male perno di selezione può causare le prestazioni di caso peggiore.In un caso ideale, il pivot sarà sempre tale che il 50% dei dati è più piccolo e il 50% dei dati è più grande, in modo che l'ingresso sarà rotto a metà, in ogni iterazione.Questo ci dà n confronto e di swap volte log 2(n) ricorsioni di O(n*logn) tempo.

Quanto costa non ideale pivot selezione influenzare il tempo di esecuzione?

Consideriamo un caso in cui il perno è costantemente scelto in modo tale che il 75% dei dati è su un lato del perno.È ancora O(n*logn), ma ora la base del log ha cambiato 1/0.75 1,33.Il rapporto in termini di prestazioni quando si cambia la base è sempre una costante rappresentata da log(2)/log(newBase).In questo caso la costante è di 2.4.Così questa qualità di pivot scelta prende 2,4 volte più a lungo rispetto a quella ideale.

Quanto velocemente questo peggiorare?

Non molto veloce fino a quando il perno scelta gets (costantemente) molto male:

50% su di un lato:(caso ideale)
75% su un lato:2.4 volte più a lungo
Il 90% su un lato:6.6 volte più a lungo
95% su un lato:13.5 volte più a lungo
99% su un lato:69 volte

Come ci si avvicina al 100% su di un lato la porzione di registro dell'esecuzione approcci n e tutta l'esecuzione asintoticamente approcci O(n^2).

In un ingenuo attuazione di QuickSort, casi come un array ordinato (per il 1 ° elemento pivot) o un reverse-array ordinato (per ultimo elemento pivot) sarà affidabile per la produzione di un caso peggiore O(n^2) tempo di esecuzione.Inoltre, le implementazioni con una prevedibile perno di selezione può essere sottoposto ad attacco DoS dati che è stato progettato per produrre di esecuzione nel caso peggiore.Moderne implementazioni evitare tutto questo con una varietà di metodi, come la randomizzazione i dati prima di ordinare, scegliendo la mediana di 3 scelti a caso gli indici, etc.Con questa casualità nel mix, abbiamo 2 casi:

Piccolo insieme di dati.Caso peggiore è ragionevolmente possibile, ma è O(n^2) non è catastrofico, perché n è abbastanza piccolo che n^2 è anche piccolo.
Grande set di dati.Caso peggiore è possibile in teoria ma non in pratica.

Quante probabilità ci sono di vedere terribile prestazioni?

Le probabilità sono infinitamente piccolo.Consideriamo una sorta di 5.000 valori:

La nostra ipotetica implementazione di scegliere un pivot che utilizza una mediana di 3 scelti a caso gli indici.Prenderemo in considerazione dei perni del 25%-75% range di essere "buono" e perni che sono a 0%-25% o 75%-100% range di essere "cattivo".Se si guarda la distribuzione di probabilità utilizzando la mediana di 3 indici random, ogni ricorsione è un 11/16 possibilità di finire con un buon pivot.Facciamo 2 conservatore (e false) ipotesi per semplificare i calcoli:

Buona perni sono sempre esattamente al 25%/75% di spalato e di operare a 2.4*caso ideale.Non abbiamo mai ottenere un ideale di divisione o di eventuali split meglio di 25/75.
Bad perni sono sempre peggiori e essenzialmente contribuire in nulla alla soluzione.

Il nostro QuickSort attuazione si ferma a n=10 e passare a un inserimento del genere, quindi abbiamo bisogno di 22 a 25%/75% pivot partizioni per rompere i 5.000 valore di input giù fino in fondo.(10*1.333333^22 > 5000) O, abbiamo bisogno di 4990 caso peggiore perni.Tenete a mente che se si accumulano 22 perni in qualsiasi punto poi il tipo si completa, quindi, il caso peggiore o qualcosa vicino si richiede estremamente la sfortuna.Se ci sono voluti 88 ricorsioni per raggiungere effettivamente il 22 perni necessario per l'ordinamento giù per n=10, che sarebbe 4*2.4*caso ideale, o circa 10 volte il tempo di esecuzione di un caso ideale.Quante probabilità ci sono che ci sarebbe non raggiungere il 22 perni dopo 88 ricorsioni?

Distribuzioni di probabilità binomiale può rispondere, e la risposta è di circa 10^-18.(n 88, k è il 21, p è 0.6875) il Tuo utente è circa mille volte più probabilità di essere colpiti da un fulmine in 1 secondo ci vuole per fare clic su [SORT] di loro per vedere che 5.000 elemento di ordinamento peggio di 10*caso ideale.Questa possibilità diventa più piccola come il set di dati diventa più grande.Qui ci sono alcune array di dimensione e il loro corrispondente possibilità di eseguire più di 10*ideale per:

Array di 640 elementi:10^-13 (richiede 15 punti di rotazione di 60 prova)
Array di 5000 articoli:10^-18 (richiede 22 perni di 88 prova)
Array di 40.000 articoli:10^-23 (richiede il 29 buona perni di 116)

Ricordate che questo è il 2 di ipotesi prudenti che sono peggio di realtà.Così le prestazioni effettive è ancora meglio, e il saldo del restante probabilità è più vicino agli ideali di quanto non.

Infine, come altri hanno detto, anche questi assurdamente improbabile casi può essere eliminato con la commutazione di un heap sort se la ricorsione stack va troppo in profondità.Così il TLDR è che, per una buona implementazioni di QuickSort, il caso peggiore in realtà non esiste perché è stata realizzata e completata l'esecuzione O(n*logn) tempo.

La risposta sarebbe inclinare leggermente verso il quicksort w.r.t a modifiche apportate con DualPivotQuickSort per i valori di base .Esso è utilizzato in JAVA 7 per ordinare in java.util.Matrici

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

È possibile trovare il JAVA7 un'implementazione qui - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Ulteriori Impressionante la Lettura su DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Merge-sort l'algoritmo generale è:

Sorta sinistra sub-array
Ordinare il diritto di sub-array
Unire i 2 ordinati sub-array

Al livello superiore, fusione di 2 ordinata sub-array coinvolge trattare con N elementi.

Un livello al di sotto che, ad ogni iterazione del passo 3 coinvolge trattare con N/2 elementi, ma è necessario ripetere questo processo due volte.Quindi stai ancora a che fare con 2 * N/2 == N elementi.

Un livello al di sotto, stai unendo 4 * N/4 == N elementi, e così via.Ogni profondità nel ricorsiva stack comporta l'unione lo stesso numero di elementi, di fronte a tutte le chiamate per la profondità.

Considerare il rapido algoritmo di ordinamento, invece:

Scegliere un punto di perno
Posizionare il punto di perno nella posizione corretta nella matrice, con tutti gli elementi più piccoli a sinistra e più a destra gli elementi
Sorta sinistra-sottomatrice
Ordinare il diritto-sottomatrice

Al livello superiore, hai a che fare con un array di dimensione N.Quindi scegliere un punto di perno, metterlo nella sua posizione corretta, e può quindi ignorare completamente per il resto dell'algoritmo.

Un livello al di sotto, hai a che fare con 2 sub-array che hanno una dimensione complessiva di N-1 (cioè sottrarre il precedente punto di perno).Si sceglie un punto di perno per ogni sub-array, che arriva fino a 2 ulteriori punti di articolazione.

Un livello al di sotto, hai a che fare con 4 sub-array, con la combinazione di dimensione N-3, per gli stessi motivi di cui sopra.

Quindi N-7...Quindi N-15...Quindi N-32...

La profondità del vostro ricorsiva stack rimane circa la stessa (logN).Con merge-sort, hai sempre a che fare con un insieme di N elementi di unione, attraverso ogni livello del ricorsiva stack.Con quick-sort, però, il numero di elementi che hai a che fare con diminuisce, come si va giù pila.Per esempio, se si guarda in profondità a metà strada attraverso il ricorsiva stack, il numero di elementi che hai a che fare con N - 2^((logN)/2)) == N - sqrt(N).

Disclaimer:Merge-sort, perché si divide l'array in esattamente 2 pezzi uguali in ogni tempo, il ricorsiva profondità è esattamente logN.Quick-sort, perché il tuo punto di perno è improbabile che sia esattamente al centro della matrice, la profondità del vostro ricorsiva stack potrebbe essere leggermente superiore a logN.Non ho fatto i calcoli per vedere quanto è grande un ruolo di questo fattore e il fattore descritto sopra, effettivamente giocare in un algoritmo di complessità.

A differenza di Merge Sort Quick Sort non utilizza un ausiliare spazio.Considerando che il Merge Sort utilizza un'ausiliaria in spazio O(n).Ma il Merge Sort è il caso peggiore complessità di O(nlogn) considerando il caso peggiore complessità del Quick Sort è O(n^2) che succede quando l'array è già ordinato.

Mentre sono entrambi nella stessa complessità di classe, che non significa che hanno la stessa fase di runtime.Quicksort è di solito più veloce di mergesort, solo perché è più facile da codice una stretta di attuazione e le operazioni che non può andare più veloce.Perché che quicksort è generalmente più veloce che la gente usa al posto del mergesort.

Però!!!Io personalmente spesso di usare mergesort o un quicksort variante che degrada verso mergesort quando quicksort fa male.Ricordate.Quicksort è solo O(n log n) media.È il caso peggiore è O(n^2)!Mergesort è sempre O(n log n).Nei casi In cui le prestazioni in realtime o la reattività è un must e i dati di input provenienti dai malintenzionati di origine, non si deve usare il normale quicksort.

Quicksort ha una media migliore complessità del caso, ma in alcune applicazioni è la scelta sbagliata.Quicksort è vulnerabile agli attacchi di negazione del servizio.Se un utente malintenzionato può scegliere l'ingresso per essere ordinati, si può facilmente costruire un set che prende il tempo del caso peggiore complessità di o(n^2).

Mergesort media complessità del caso e caso peggiore complessità sono le stesse, e, come tale, non soffre lo stesso problema.Questa struttura di tipo merge-sort, inoltre, rende la scelta ideale per sistemi real-time - proprio perché non ci sono casi patologici che causano a correre molto, molto più lento.

Io sono un grande fan di Mergesort che io sono di Quicksort, per questi motivi.

Perché Quicksort è buono?

QuickSort si N^2 nel caso peggiore e NlogN caso medio.Il caso peggiore si verifica quando i dati vengono ordinati.Questo può essere mitigata casuale (shuffle prima di ordinare è iniziato.
QuickSort non richiede memoria aggiuntiva che viene preso da un merge sort.
Se il set di dati è grande e non ci sono elementi identici, la complessità di Quicksort riduce utilizzando 3 vie partizione.Più il numero di oggetti identici meglio ordinamento.Se tutti gli elementi sono identici, è sorta in un tempo lineare.[Questo è l'implementazione di default nella maggior parte delle biblioteche]

È Quicksort sempre meglio di Mergesort?

Non proprio.

Mergesort è stabile, ma Quicksort non è.Quindi, se si bisogno di stabilità in uscita, utilizzare Mergesort.La stabilità è necessaria in molte applicazioni pratiche.
La memoria è a buon mercato al giorno d'oggi.Quindi, se la memoria aggiuntiva, utilizzato da Mergesort non è fondamentale per la vostra applicazione, non c'è nulla di male nell'utilizzo di Mergesort.

Nota: In java gli Array.funzione sort() utilizza Quicksort per tipi di dati primitivi e Mergesort per oggetto i tipi di dati.Poiché gli oggetti consumare overhead di memoria, quindi, aggiunto un po ' di overhead per Mergesort può essere un problema per il punto di vista del rendimento.

Riferimento:Guarda il video di QuickSort 3 settimane, Princeton Algoritmi Corso di Coursera

Quick sort è il caso peggiore O(n^2), tuttavia, il caso medio costantemente eseguito il merge sort.Ogni algoritmo è O(nlogn), ma è necessario ricordare che quando si parla di Grandi O lasciare fuori il minore complessità di fattori.Quick sort ha significativi miglioramenti rispetto merge sort quando si tratta di fattori costanti.

Merge sort, inoltre, richiede O(2n) di memoria, mentre una rapida ordinamento può essere fatto in un posto (che richiede solo O(n)).Questo è un altro motivo che quick sort è generalmente preferito oltre il merge sort.

Extra info:

Il caso peggiore di quick sort si verifica quando il perno è scelto male.Si consideri il seguente esempio:

[5, 4, 3, 2, 1]

Se il perno è scelto come il più piccolo o il più grande numero in poi il gruppo quick sort verrà eseguito in O(n^2).La probabilità di scegliere l'elemento che è più piccolo o più grande del 25% della lista è di 0,5.Che dà l'algoritmo 0,5 possibilità di essere un buon pivot.Se ci avvaliamo di un tipico pivot scelta di algoritmo (a dire la scelta di un elemento casuale), abbiamo 0.5 possibilità di scelta di un buon pivot per ogni scelta di un pivot.Per le collezioni di grandi dimensioni la probabilità che scegliendo sempre un povero pivot è di 0,5 * n.Basato sulla probabilità di quick sort è efficiente per la media (e tipico) caso.

Questa è una bella domanda, ma dal momento che ho avuto a che fare con entrambi recentemente qui sono i miei 2c:

Merge sort esigenze in media ~ N log N i confronti.Già (quasi) ordinati ordinati matrici questo arriva fino a 1/2 N log N, dal momento che durante la fusione abbiamo (quasi) sempre, selezionare "sinistra" parte 1/2 N di volte e poi basta copiare a destra e 1/2 di N elementi.Inoltre posso ipotizzare che già ordinato un input di processore branch predictor brillare ma indovinando quasi tutti i rami correttamente, impedendo così pipeline bancarelle.

Quick sort, in media, richiede ~ 1.38 N log N i confronti.Non beneficiano notevolmente già array ordinato in termini di confronti (ma non in termini di swap e, probabilmente, in termini di ramo previsioni all'interno della CPU).

Il mio benchmark abbastanza processore moderno, presenta i seguenti:

Quando confronto la funzione è una funzione di callback (come in qsort() libc attuazione) quicksort è più lento di mergesort del 15% su input casuale e del 30% per già array ordinato per gli interi a 64 bit.

D'altra parte, se il confronto non è un callback, la mia esperienza è che quicksort supera mergesort fino al 25%.

Tuttavia, se la (grande) la matrice ha pochi valori univoci, merge sort inizia a guadagnare oltre quicksort in ogni caso.

Quindi, forse, la linea di fondo è:se il confronto è costoso (ad es.funzione di callback, confrontare le stringhe, il confronto di molte parti di una struttura per lo più raggiungere un secondo-terzo-quarto "se" fare la differenza) - le probabilità sono che voi sarà meglio con il merge sort.Per i compiti più semplici quicksort sarà più veloce.

Che ha detto in precedenza detto è vero:- Quicksort può essere di N^2, ma Sedgewick afferma che una buona randomizzati attuazione ha più probabilità di un computer che esegue sorta di essere colpito da un fulmine, di N^2 - Mergesort richiede spazio aggiuntivo

Quando ho sperimentato sia algoritmi di ordinamento, contando il numero di chiamate ricorsive, quicksort dispone costantemente di meno chiamate ricorsive di mergesort.È perché quicksort ha perni e perni non sono inclusi nel prossimo chiamate ricorsive.Che modo quicksort può raggiungere ricorsiva di base più veloce rispetto a mergesort.

Tutte le cose sono uguali, mi sarei aspettato maggior parte delle persone di utilizzare ciò che è più conveniente disponibile, e che tende ad essere qsort(3).Più che altro quicksort è noto per essere molto veloce su array, proprio come mergesort è la scelta più comune per le liste.

Quello che mi chiedo è perché è così raro vedere radix o secchio di sorta.Sono O(n), almeno su liste collegate e tutto ciò che serve è qualche metodo per convertire la chiave per un numero ordinale.(stringhe e galleggia bene.)

Sto pensando che la ragione ha a che fare con il modo in informatica viene insegnata.Ho anche dovuto dimostrare al mio docente di Algoritmo di analisi che è stato possibile infatti ordinare più velocemente rispetto a O(n log(n)).(Ha avuto la prova che non si può confronto ordinare più velocemente rispetto a O(n log(n)), che è vero.)

In altre notizie, i galleggianti possono essere ordinati come numeri interi, ma devi girare i numeri negativi in giro dopo.

Edit:In realtà, qui è ancora più vizioso modo per ordinare i carri-come-interi: http://www.stereopsis.com/radix.html.Nota che il capovolgimento di bit trucco può essere utilizzato indipendentemente da cosa algoritmo di ordinamento è effettivamente utilizzare...

È difficile da dire.Il peggiore di MergeSort è n(log2n)-n+1,che è accurato se n è uguale a 2^k(ho già provato questa).E, per ogni n,tra le (n lg n - n + 1) (n lg n + n + O(lg n)).Ma per il quickSort,meglio è nlog2n(anche n è uguale a 2^k).Se si divide Mergesort da quickSort,è uguale a uno se n è infinito.Quindi è come se il caso peggiore di MergeSort è il migliore in assoluto caso di QuickSort,perché facciamo uso di quicksort?Ma ricordate,MergeSort non è a posto,si richiede 2n memeroy spazio.E MergeSort anche bisogno di fare molti matrice di copie,che non sono incluse nell'analisi di un algoritmo.In una parola,MergeSort è davvero faseter di quicksort piano teorico,ma in realtà è necessario considerare di spazio disco spazio,il costo della copia dell'array,la fusione è più lento di quick sort.Una volta ho fatto un esperimento in cui mi è stata data 1000000 cifre in java, classe Random,e ci sono voluti 2610ms da mergesort,1370ms da quicksort.

Piccole aggiunte di rapida vs unione di sorta.

Inoltre, esso può dipendere dal tipo di ordinamento di elementi.Se l'accesso agli elementi, di scambio e confronto non è delle più semplici operazioni, come il confronto di numeri interi in aereo memoria, quindi il merge sort può essere preferibile algoritmo.

Ad esempio , è possibile ordinare gli elementi utilizzando il protocollo di rete su server remoto.

Inoltre, in contenitori personalizzati come "lista", non c'è nessun vantaggio di un rapido sorta.
1.Merge sort legato elenco, non hanno bisogno di ulteriore memoria.2.Accesso agli elementi di quick sort non è sequenziale (in memoria)

Quick sort è un algoritmo di ordinamento, quindi è più adatto per le matrici.Merge sort d'altra parte, richiede l'extra storage di O(N), ed è più adatto per le liste collegate.

A differenza delle matrici, in piaceva elenco possiamo inserire elementi nel mezzo, con O(1) e O(1) e, di conseguenza, l'operazione di unione di tipo merge sort può essere implementato senza spazio extra.Tuttavia, l'allocazione e la deallocazione di spazio extra per le matrici che hanno un effetto negativo sul tempo di esecuzione di merge sort.Merge sort favorisce anche un elenco collegato come si accede ai dati in modo sequenziale, senza molto casuale di accesso alla memoria.

Quick sort d'altra parte, richiede un sacco di memoria casuale di accesso e con un array possiamo accedere direttamente alla memoria, senza alcun attraversamento, come richiesto dalle liste collegate.Anche quick sort quando utilizzato per le matrici che hanno un buon località di riferimento, come gli array sono memorizzati in modo contiguo in memoria.

Anche se i due algoritmi di ordinamento media complessità è O(NlogN), di solito la gente per le attività di ordinaria utilizza un array di archiviazione, e per questo motivo quick sort dovrebbe essere l'algoritmo di scelta.

EDIT:Ho appena scoperto che il merge sort peggiore/migliore/avg caso è sempre nlogn, ma quick sort può variare da n2(caso peggiore quando gli elementi sono già ordinati) per nlogn(avg/migliore dei casi, quando pivot sempre divide l'array in due metà).

Considerare il tempo e lo spazio complessità sia.Per il Merge sort :Il tempo di complessità :O(nlogn) , Spazio complessità :O(nlogn)

Per il Quick sort :Il tempo di complessità :O(n^2) , Spazio complessità :O(n)

Ora, entrambi vincono in uno scenerio ogni.Ma, utilizzando un casuale pivot quasi sempre è possibile ridurre la complessità di Quick sort a O(nlogn).

Così, Quick sort è preferito in molte applicazioni, invece di Merge sort.

In c/c++ terra, quando non si utilizzano contenitori stl, io tendo a usare il quicksort, perché è costruito in fase di esecuzione, mentre mergesort non è.

Quindi credo che, in molti casi, è semplicemente il percorso di minor resistenza.

Inoltre, le prestazioni possono essere molto più alto con quick sort, per i casi in cui l'intero set di dati, non rientra nel working set.

Uno dei motivi è più filosofico.Quicksort è Top->Down filosofia.Con n elementi da ordinare, ci sono n!possibilità.Con 2 partizioni di m & n-m, che si escludono a vicenda, il numero di possibilità di andare in diversi ordini di grandezza.m!* (n-m)!è più piccolo di molti ordini di n!da solo.immaginate di 5!vs 3!*2!.5!è 10 volte più possibilità di 2 partizioni di 2 e 3 ciascuno .e estrapolare a 1 milione di fattoriale vs 900K!*100K!vsCosì, invece di preoccuparsi di stabilire qualsiasi ordine all'interno di un intervallo o una partizione,solo di ristabilire l'ordine in un più ampio livello di partizioni e di ridurre la possibilità all'interno di una partizione.Qualsiasi ordine stabilito in precedenza all'interno di un range di essere disturbati in seguito, se le partizioni stesse non si escludono a vicenda.

Qualsiasi basso ordine di un approccio come il merge sort o heap sort è come operai o di un dipendente di un approccio in cui si inizia il confronto a livello microscopico presto.Ma questo ordine non è destinata ad essere persa come presto come un elemento tra di loro si ritrovano.Questi approcci sono molto stabili e molto prevedibile, ma fare una certa quantità di lavoro extra.

Quick Sort è come approccio Manageriale in cui uno non è inizialmente preoccupato per qualsiasi ordine , solo circa la riunione di un ampio criterio, Senza riguardo per l'ordine.Le partizioni sono restringere fino ad ottenere un insieme ordinato.La vera sfida in Quicksort è nella ricerca di una partizione o di un criterio nel buio quando si sa nulla circa gli elementi da ordinare.Che è il motivo per cui ci sia bisogno di spendere un po ' di sforzo per trovare un valore mediano o pick 1 in modo casuale o arbitrario "Gestionale" approccio .Per trovare un perfetto mediana può assumere notevole quantità di sforzo e porta a una stupida approccio bottom-up di nuovo.Così Quicksort dice solo una scelta un casuale pivot e la speranza che possa essere da qualche parte nel mezzo o fare qualche lavoro per trovare la mediana di 3 , 5 o qualcosa di più per trovare una migliore mediana, ma pensa di non essere perfetto e non perdere tempo in prima ordinazione.Che sembra fare bene, se siete fortunati, o a volte si riduce a n^2 quando non si ottiene un mediano, ma semplicemente prendere una possibilità.Alcun modo dei dati è casuale.destra.Quindi io sono d'accordo di più con il top ->down approccio logico di quicksort & si scopre che la possibilità che ci vogliono circa pivot selezione e i confronti che si salva in precedenza sembra funzionare meglio più volte di qualsiasi meticolosa & approfondita stabile di fondo ->approccio come il merge sort.Ma

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow