Hoekom is quicksort beter as mergesort?

https://stackoverflow.com/questions/70402

09-06-2019
|

Vra

Ek is hierdie vraag tydens 'n onderhoud gevra.Hulle is albei O(nlogn) en tog gebruik die meeste mense Quicksort in plaas van Mergesort.Hoekom is dit?

Oplossing

Quicksort het O ( n ²) ergste geval runtime en O gemiddelde ( n n te meld) geval runtime. Dit is egter beter om saam te smelt soort in baie scenario's as gevolg van verskeie faktore runtime 'n algoritme se beïnvloed, en toe neem hulle almal saam, quicksort wen nie.

In die besonder, die dikwels-aangehaalde runtime van sorteeralgoritmes verwys na die aantal vergelykings of die getal van swaps wat nodig is om uit te voer om die data te sorteer. Dit is inderdaad 'n goeie maatstaf van prestasie, veral omdat dit is onafhanklik van die onderliggende hardeware-ontwerp. Maar ander dinge - soos ligging van verwysing (maw lees ons baie van die elemente wat waarskynlik in die kas?) - ook 'n belangrike rol speel op huidige hardeware. Quicksort in die besonder verg min bykomende ruimte en uitstallings goeie kas plek, en dit maak dit vinniger as saamsmelt soort in baie gevalle.

Verder, dit is baie maklik om te quicksort se ergste hardloop tyd van O vermy ( n ²) byna geheel en al deur die gebruik van 'n geskikte keuse van die spilpunt - soos pluk dit na willekeur (hierdie is 'n uitstekende strategie).

In die praktyk, baie modern implementering van quicksort (in die besonder libstdc ++ se std::sort) is eintlik introsort , wie se teoretiese ergste geval is O ( n aanteken n ), dieselfde as merge soort. Dit word gedoen deur die beperking van die rekursie diepte, en oor te skakel na 'n ander algoritme ( heapsort ) wanneer dit oorskry teken n .

Ander wenke

Soveel mense het opgemerk, die gemiddelde geval prestasie vir quicksort is vinniger as mergesort. Maar hierdie is net waar as jy konstante tyd is die veronderstelling om toegang te verkry tot enige stuk van die geheue op aanvraag.

In RAM hierdie aanname is oor die algemeen nie te sleg nie (dit is nie altyd waar nie as gevolg van caches, maar dit is nie te sleg nie). Maar as jou data struktuur is groot genoeg om te lewe op die skyf, dan quicksort kry vermoor deur die feit dat jou gemiddelde skyf nie iets soos 200 ewekansige soek per sekonde. Maar daardie selfde skyf het lees of skryf nie moeilikheid megagrepe per sekonde van data agtermekaar. Dit is presies wat mergesort doen.

Daarom, as data moet word gesorteer op skyf, jy regtig, regtig wil 'n paar variasies op mergesort gebruik. (Oor die algemeen jy quicksort sublists, dan begin hulle saam samesmelting bo 'n paar grootte drumpel.)

Verder as wat jy hoef te doen enigiets met datastelle van daardie grootte, dink hard oor hoe om te verhoed dat poog om die skyf. Byvoorbeeld is dit die rede waarom dit is standaard raad wat jy laat val indekse voor doen groot data vragte in databasisse, en dan weer op te bou die indeks later. Die handhawing van die indeks gedurende die vrag beteken voortdurend op soek na skyf. In teenstelling hiermee as jy die indekse daal, dan die databasis kan die indeks weer op te bou deur eers die inligting te hanteer (met behulp van 'n mergesort natuurlik!) En dan laai dit in 'n BTREE datastructure vir die indeks sorteer. (BTREEs is natuurlik gehou ten einde, sodat jy kan 'n mens van 'n gesorteerde datastel met 'n paar soek op jou hardeskyf te laai.)

Daar is 'n aantal geleenthede waar die begrip van hoe om die hardeskyf te vermy gewees soek het my laat maak werk dataverwerking neem ure eerder as dae of weke.

Eintlik QuickSort is O (n ²). Sy gemiddelde geval loop tyd is O (nlog (n)), maar sy ergste is O (n ²), wat plaasvind wanneer jy dit uit te voer op 'n lys wat min unieke items bevat. Randomisasie neem O (n). Natuurlik is dit nie die ergste geval verander, is dit net verhoed dat 'n kwaadwillige gebruiker van die maak van jou soort neem 'n lang tyd.

QuickSort is meer gewild omdat dit:

Is in-place (MergeSort vereis ekstra geheue lineêre aan aantal elemente word gesorteer).
'n klein verborge konstante.

"en nog die meeste mense gebruik Quicksort in plaas van Mergesort. Hoekom is dit?"

Een sielkundige rede wat nie gegee is eenvoudig dat Quicksort is meer slim genoem. dit wil sê 'n goeie bemarking.

Ja, Quicksort met triple partioning is waarskynlik een van die beste algemene doel soort algoritmes, maar Theres geen kry oor die feit dat "Quick" soort klink baie meer kragtig as "Merge" soort.

Soos ander het opgemerk, ergste geval van Quicksort is O (n ^ 2), terwyl mergesort en heapsort bly by O (nlogn). Op die gemiddelde geval, egter, al drie is O (nlogn); so dit is vir die oorgrote meerderheid van gevalle vergelykbaar.

Wat maak Quicksort beter gemiddeld is dat die innerlike lus impliseer vergelyk verskeie waardes met 'n enkele een, terwyl hy op die ander twee beide terme is verskillend vir elke vergelyking. Met ander woorde, Quicksort doen helfte soveel lui soos die ander twee algoritmes. Op moderne SVE's prestasie is swaar gedomineer deur toegang tye, so op die ou end beland Quicksort om 'n goeie eerste keuse.

Ek wil byvoeg dat van die drie tot dusver genoem (mergesort, quicksort en hoop soort) algoritmes net mergesort is stabiel. Dit wil sê, die einde nie verander nie vir daardie waardes wat dieselfde sleutel het. In sommige gevalle is dit wenslik.

Maar, die waarheid vertel word, in praktiese situasies die meeste mense nodig het net goeie gemiddelde prestasie en quicksort is ... vinnige =)

Alle soort algoritmes het hul lief en leed. Sien Wikipedia artikel vir sorteeralgoritmes vir 'n goeie oorsig.

Van die Wikipedia-inskrywing op Quicksort :

Quicksort kompeteer ook met mergesort, 'n ander rekursiewe soort algoritme maar met die voordeel van ergste geval Θ (nlogn) hardloop tyd. Mergesort is 'n stabiele soort, in teenstelling met quicksort en heapsort, en kan wees maklik aangepas word om te werk op gekoppelde lyste en baie groot lyste gestoor word op stadig-to-toegang media soos skyf stoor of netwerk aangeheg stoor. Hoewel quicksort geskryf kan word om werk op geskakelde lyste, sal dit dikwels ly aan swak spilpunt keuses sonder ewetoeganklike. Die grootste nadeel van mergesort is dat, wanneer die bedryf op skikkings, dit vereis Θ (n) hulp ruimte in die beste geval, terwyl die variant van quicksort met in-plek skeiding en stert rekursie gebruike net Θ (logn) ruimte. (Let daarop dat wanneer wat op geskakelde lyste, mergesort vereis slegs 'n klein, konstante bedrag van hulp stoor.)

Mu! Quicksort is nie beter, dit is geskik vir 'n ander soort van aansoek, as mergesort.

Mergesort is die moeite werd oorweging as spoed is van die essensie, slegte ergste prestasie kan nie geduld word nie, en ekstra ruimte is beskikbaar. 1

Jy verklaar dat hulle «Hulle is albei O (nlogn) [...]». Dis verkeerd. «Quicksort gebruik oor N ^ 02/02 vergelykings in die ergste geval.» 1 .

Maar die belangrikste eiendom volgens my ervaring is die maklike implementering van sekwensiële toegang wat jy kan gebruik terwyl sorteer by die gebruik van programmeertale met die noodsaaklikheid paradigma.

1 Sedgewick, algoritmes

Quicksort is die vinnigste sorteer algoritme in die praktyk, maar het 'n aantal patologiese gevalle wat kan maak dat dit uit te voer so erg soos O (n2).

Heapsort is gewaarborg om te hardloop in O (n * ln (n)) en vereis slegs beperkte ekstra stoorplek. Maar daar is baie aanhalings van werklike wêreld toetse wat wys dat heapsort is aansienlik stadiger as quicksort gemiddeld.

Wikipedia se verduideliking is:

Tipies, quicksort is aansienlik vinniger in die praktyk as ander Θ (nlogn) algoritmes, want sy binneste lus doeltreffend geïmplementeer kan word op die meeste platforms, en in die meeste werklike wêreld data is dit moontlik om die ontwerp keuses wat die waarskynlikheid van die minimum te beperk maak vereis kwadratiese tyd.

Quicksort

Mergesort

Ek dink daar is ook probleme met die bedrag van die stoor wat nodig is vir Mergesort (wat Ω (n)) wat quicksort implementering nie. In die ergste geval, hulle is dieselfde bedrag van algoritmiese tyd, maar mergesort vereis meer stoorplek.

Quicksort is nie beter as mergesort. Met O (n ^ 2) (ergste geval wat selde gebeur), quicksort is potensieel baie stadiger as die O (nlogn) van die merge soort. Quicksort het minder oorhoofse, so met 'n klein N en stadige rekenaars, is dit beter. Maar rekenaars is so vinnig vandag dat die bykomende oorhoofse van 'n mergesort is weglaatbaar, en die risiko van 'n baie stadige quicksort ver swaarder weeg as die onbeduidende oorhoofse van 'n mergesort in die meeste gevalle.

Verder is 'n mergesort laat items met identiese sleutels in hul oorspronklike bevel, 'n nuttige kenmerk.

Ek wil graag 'n bietjie wiskunde byvoeg oor hoe QuickSort presteer wanneer dit van die beste geval afwyk en hoe waarskynlik dit is, wat ek hoop mense sal help om 'n bietjie beter te verstaan hoekom die O(n^2) geval nie werklik is nie kommer oor die meer gesofistikeerde implementering van QuickSort.

Buiten ewekansige toegangskwessies is daar twee hooffaktore wat die prestasie van QuickSort kan beïnvloed en hulle hou albei verband met hoe die spilpunt vergelyk met die data wat gesorteer word.

1) 'n Klein aantal sleutels in die data.'n Datastel met almal dieselfde waarde sal in n^2 tyd op 'n vanielje 2-partisie QuickSort sorteer omdat al die waardes behalwe die spilpunt elke keer aan die een kant geplaas word.Moderne implementerings spreek dit aan deur metodes soos die gebruik van 'n 3-partisie-soort.Hierdie metodes word uitgevoer op 'n datastel van almal dieselfde waarde in O(n) tyd.Die gebruik van so 'n implementering beteken dus dat 'n inset met 'n klein aantal sleutels eintlik prestasietyd verbeter en nie meer 'n bekommernis is nie.

2) Uiters swak spilpuntkeuse kan die slegste geval prestasie veroorsaak.In 'n ideale geval sal die spilpunt altyd so wees dat 50% die data kleiner is en 50% die data groter is, sodat die invoer in die helfte gebreek sal word tydens elke iterasie.Dit gee ons n vergelykings en ruil tye log-2(n) rekursies vir O(n*logn) tyd.

Hoeveel beïnvloed nie-ideale spilpuntkeuse uitvoeringstyd?

Kom ons kyk na 'n geval waar die spilpunt konsekwent so gekies word dat 75% van die data aan die een kant van die spilpunt is.Dit is steeds O(n*logn), maar nou het die basis van die log verander na 1/0.75 of 1.33.Die verhouding in prestasie wanneer die basis verander word, is altyd 'n konstante verteenwoordig deur log(2)/log(newBase).In hierdie geval is daardie konstante 2,4.Hierdie kwaliteit van spilpuntkeuse neem dus 2,4 keer langer as die ideaal.

Hoe vinnig word dit erger?

Nie baie vinnig totdat die spilpuntkeuse (konsekwent) baie sleg word nie:

50% aan die een kant:(ideale geval)
75% aan die een kant:2,4 keer so lank
90% aan die een kant:6,6 keer so lank
95% aan die een kant:13,5 keer so lank
99% aan die een kant:69 keer so lank

Soos ons 100% aan die een kant nader, nader die loggedeelte van die uitvoering n en die hele uitvoering nader asimptoties O(n^2).

In 'n naïewe implementering van QuickSort, sal gevalle soos 'n gesorteerde skikking (vir 1ste element spilpunt) of 'n omgekeerde gesorteerde skikking (vir laaste element spilpunt) betroubaar 'n slegste geval O(n^2) uitvoeringstyd produseer.Boonop kan implementerings met 'n voorspelbare spilpuntkeuse aan DoS-aanval onderwerp word deur data wat ontwerp is om die ergste geval uitvoering te produseer.Moderne implementerings vermy dit deur 'n verskeidenheid metodes, soos om die data te ewekansig te maak voor sorteer, die keuse van die mediaan van 3 ewekansig gekose indekse, ens.Met hierdie ewekansigheid in die mengsel het ons 2 gevalle:

Klein datastel.Die ergste geval is redelik moontlik, maar O(n^2) is nie katastrofies nie, want n is klein genoeg dat n^2 ook klein is.
Groot datastel.Die ergste geval is moontlik in teorie, maar nie in die praktyk nie.

Hoe waarskynlik is dit dat ons verskriklike prestasie sal sien?

Die kanse is verdwynend klein.Kom ons kyk na 'n soort van 5 000 waardes:

Ons hipotetiese implementering sal 'n spilpunt kies deur 'n mediaan van 3 ewekansig gekose indekse te gebruik.Ons sal spilpunte wat in die 25%-75%-reeks is as "goed" beskou en spilpunte wat in die 0%-25%- of 75%-100%-reeks is as "sleg".As jy na die waarskynlikheidsverdeling kyk deur die mediaan van 3 ewekansige indekse te gebruik, het elke rekursie 'n 11/16 kans om met 'n goeie spilpunt te eindig.Kom ons maak 2 konserwatiewe (en vals) aannames om die wiskunde te vereenvoudig:

Goeie spilpunte is altyd presies op 'n 25%/75% verdeling en werk teen 2.4* ideale geval.Ons kry nooit 'n ideale verdeling of enige verdeling beter as 25/75 nie.
Slegte spilpunte is altyd die ergste geval en dra in wese niks by tot die oplossing nie.

Ons QuickSort-implementering sal stop by n=10 en oorskakel na 'n invoegingssoort, so ons benodig 22 25%/75% spilpuntpartisies om die 5 000 waarde-invoer so ver af te breek.(10*1.333333^22 > 5000) Of, ons benodig 4990 ergste spilpunte.Hou in gedagte dat as ons ophoop 22 goeie spilpunte by enige punt dan sal die sorteer voltooi word, so worst case of enigiets naby dit vereis uiters slegte geluk.As dit ons 88 rekursies geneem het om werklik die 22 goeie spilpunte te bereik wat nodig is om af te sorteer na n=10, sou dit 4*2.4* ideale geval of ongeveer 10 keer die uitvoeringstyd van die ideale geval wees.Hoe waarskynlik is dit dat ons sou nie bereik die vereiste 22 goeie spilpunte na 88 rekursies?

Binomiale waarskynlikheidsverdelings kan dit antwoord, en die antwoord is omtrent 10^-18.(n is 88, k is 21, p is 0,6875) Jou gebruiker is ongeveer 'n duisend keer meer geneig om deur weerlig getref te word in die 1 sekonde wat dit neem om [SORT] te klik as wat hulle is om te sien dat 5 000 items sorteer hardloop enige erger as 10* ideale geval.Hierdie kans word kleiner namate die datastel groter word.Hier is 'n paar skikkingsgroottes en hul ooreenstemmende kanse om langer as 10* ideaal te loop:

Skikking van 640 items:10^-13 (vereis 15 goeie spilpunte uit 60 drieë)
Skikking van 5 000 items:10^-18 (vereis 22 goeie spilpunte uit 88 drieë)
Skikking van 40 000 items: 10^-23 (vereis 29 goeie spilpunte uit 116)

Onthou dat dit met 2 konserwatiewe aannames is wat erger is as die werklikheid.Die werklike prestasie is dus nog beter, en die balans van die oorblywende waarskynlikheid is nader aan ideaal as nie.

Ten slotte, soos ander genoem het, kan selfs hierdie absurd onwaarskynlike gevalle uitgeskakel word deur na 'n hoopsoort oor te skakel as die rekursiestapel te diep gaan.Die TLDR is dus die ergste geval vir goeie implementering van QuickSort bestaan nie regtig nie want dit is ontwerp en uitvoering voltooi in O(n*logn) tyd.

Die antwoord sal effens kantel die rigting van quicksort w.r.t om veranderinge gebring met DualPivotQuickSort vir primitiewe waardes. Dit word gebruik in JAVA 7 uit te sorteer in java.util.Arrays

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.

Jy kan die JAVA7 implmentation hier vind - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Verder awesome Lees op DualPivotQuickSort - http: // permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

In merge-soort, die algemene algoritme is:

Sorteer links sub-array
sorteer die regte sub-array
Merge die 2 gesorteer sub-skikkings

Op die boonste vlak, die samesmelting van die 2 gesorteer sub-skikkings behels die hantering van N elemente.

Een vlak laer as dié, elke iterasie van stap 3 behels die hantering van N / 2 elemente, maar jy moet hierdie proses twee keer herhaal. So jy nog steeds die hantering van 2 * N / 2 == N elemente.

Een vlak laer as dié, jy samesmelting 4 * N / 4 == N elemente, en so aan. Elke diepte in die rekursiewe stapel behels die samesmelting van dieselfde aantal elemente, oor al die oproepe vir daardie diepte.

Kyk na die vinnige soort algoritme plaas:

Kies 'n spilpunt
Plaas die spilpunt op die regte plek in die skikking, met al kleiner elemente aan die linkerkant, en groter elemente om die regte
Sorteer links-subarray
sorteer die regte-subarray

Op die boonste vlak, jy doen met 'n verskeidenheid van grootte N. Jy kies dan een spilpunt, sit dit in sy regte posisie, en kan dan ignoreer dit heeltemal vir die res van die algoritme.

Een vlak laer as dié, jy te doen het met 2 sub-skikkings wat 'n gekombineerde grootte van N-1 het (dit wil sê, trek die vorige spilpunt). Jy kies 'n spilpunt vir elke sub-skikking, wat kom tot 2 addisionele spilpunt punte.

Een vlak laer as dié, jy te doen het met 4 sub-skikkings met gekombineerde grootte N-3, vir dieselfde redes as hierbo.

Toe N-7 ... Dan N-15 ... Dan N-32 ...

Die diepte van jou rekursiewe stapel bly min of meer dieselfde (logn). Met merge-soort, jy altyd doen met 'n N-element merge, oor elke vlak van die rekursiewe stapel. Met 'n vinnige-soort alhoewel, die aantal elemente wat jy te doen het met aansien soos jy gaan af in die stapel. Byvoorbeeld, as jy kyk na die diepte halfpad deur die rekursiewe stapel, die aantal elemente wat jy te doen het met is N - 2 ^ ((logn) / 2)) == N -. Sqrt (N)

Disclaimer: Op merge-soort, omdat jy die skikking te verdeel in 2 presies gelyk stukke elke keer, die rekursiewe diepte is presies logn. Op 'n vinnige-soort, omdat jou spilpunt is onwaarskynlik dat presies in die middel van die skikking, die diepte van jou rekursiewe stapel kan effens groter as logn wees. Ek het nie die wiskunde gedoen hoe groot 'n rol hierdie faktor en die hierbo beskryf faktor om te sien, eintlik speel in kompleksiteit van die algoritme se.

In teenstelling met Merge Sorteer Quick Sorteer nie gebruik van 'n auxilary ruimte. Terwyl Merge Sorteer gebruik van 'n auxilary ruimte O (n). Maar Merge Sorteer het die ergste geval tyd kompleksiteit van O (nlogn) terwyl die ergste geval kompleksiteit van Quick Sorteer is O (n ^ 2) wat gebeur wanneer die skikking is reeds gesorteer is.

Hoewel hulle is albei in dieselfde kompleksiteit klas, dit beteken nie dat hulle albei dieselfde runtime. Quicksort is gewoonlik vinniger as mergesort, net omdat dit makliker is om 'n stywe implementering en die bedrywighede dit nie kan vinniger gaan code. Dit is omdat dit quicksort is oor die algemeen vinniger wat mense gebruik dit in plaas van mergesort.

Maar! Ek sal persoonlik dikwels mergesort of 'n quicksort variant wat afbreek om mergesort wanneer quicksort swak doen te gebruik. Onthou. Quicksort is slegs O (n teken N) op gemiddelde . Dit is die ergste geval is O (n ^ 2)! Mergesort is altyd O (n teken N). In gevalle waar realtime prestasie of reaksie is 'n moet en jou insette data kan kom uit 'n kwaadwillige bron, jy moet nie gebruik plain quicksort.

Quicksort het 'n beter gemiddelde geval kompleksiteit maar in sommige aansoeke is dit die verkeerde keuse. Quicksort is kwesbaar vir ontkenning van die diens aanvalle. As 'n aanvaller die insette kan kies om gesorteer, kan hy maklik 'n stel wat die ergste geval tyd kompleksiteit van o neem (n ^ 2).

Mergesort se gemiddelde geval kompleksiteit en die ergste geval kompleksiteit is dieselfde, en as sodanig het dieselfde probleem nie ly. Hierdie eiendom van merge-soort maak dit die beter keuse vir real-time stelsels ook - juis omdat daar nie patologiese gevalle wat veroorsaak dat dit baie, baie stadiger hardloop.

Ek is 'n groter fan van Mergesort as ek van Quicksort, vir hierdie rede.

Hoekom Quicksort is goed?

QuickSort neem N ^ 2 in die ergste geval en NlogN gemiddelde geval. Die ergste geval vind plaas wanneer data gesorteer. Dit kan verminder word deur random shuffle voor sorteer begin.
QuickSort nie neem ekstra geheue wat geneem word deur merge soort.
As die dataset is groot en daar is identies items, kompleksiteit van Quicksort verminder deur die gebruik van 3 manier partisie. Meer die geen identiese items beter die soort. As al die items is identies, dit sorteer in lineêre tyd. [Dit is standaard implementering in die meeste biblioteke]

Is Quicksort altyd beter as Mergesort?

Nie regtig nie.

Mergesort is stabiel, maar Quicksort is nie. So as jy stabiliteit nodig in die produksie, sal jy Mergesort gebruik. Stabiliteit nodig is in baie praktiese toepassings.
Memory is goedkoop deesdae. So as ekstra geheue wat gebruik word deur Mergesort is nie van kritieke belang om jou aansoek, daar is geen skade in die gebruik van Mergesort.

Nota: in Java, Arrays.sort () funksie gebruik Quicksort vir primitiewe datatipes en Mergesort vir datatipes voorwerp. Omdat voorwerpe te vernietig geheue oorhoofse, so het bygevoeg 'n bietjie oorhoofse vir Mergesort mag nie enige kwessie vir prestasie oogpunt.

Reference : Kyk na die QuickSort videos van Week 3, Princeton algoritmes Kursus by Coursera

Quick soort is die ergste geval O (n ^ 2), maar die gemiddelde geval konsekwent uit voer saamsmelt soort. Elke algoritme is O (nlogn), maar wat jy nodig het om te onthou dat wanneer dit oor Big O ons laat vaar die laer kompleksiteit faktore. Vinnige soort het beduidende verbeterings oor merge soort wanneer dit kom by konstante faktore.

Merge soort ook vereis O (2n) geheue, terwyl vinnige soort kan gedoen word in plaas (wat net O (n)). Dit is nog 'n rede dat 'n vinnige soort algemeen verkies word bo merge soort.

Ekstra info:

Die ergste geval van 'n vinnige soort kom voor wanneer die spilpunt swak gekies. Kyk na die volgende voorbeeld:

[5, 4, 3, 2, 1]

As die spilpunt is gekies as die kleinste of grootste getal in die groep dan sal vinnig soort hardloop in O (n ^ 2). Die waarskynlikheid van die keuse van die element wat in die grootste of kleinste 25% van die lys is 0,5. Dit gee die algoritme 'n 0,5 kans om 'n goeie losskakel. As ons in diens 'n tipiese spilpunt keuse algoritme (sê die keuse van 'n ewekansige element), ons het 0,5 kans keuse van 'n goeie spilpunt vir elke keuse van 'n spilpunt. Vir versamelings van 'n groot omvang van die waarskynlikheid van altyd die keuse van 'n swak spilpunt is 0,5 * n. Op grond van hierdie waarskynlikheid vinnige soort is doeltreffend vir die gemiddelde (en tipies) geval.

Dit is 'n mooi ou vraag, maar sedert ek het gehandel oor beide onlangs hier is my 2c:

Merge soort nodig gemiddeld ~ N teken N vergelykings. Vir al (byna) gesorteer gesorteer skikkings kry dit neer op 1/2 N log N, aangesien terwyl die samesmelting van ons (byna) altyd kies "links" deel 1/2 N kere en dan net reg 1/2 N elemente kopieer. Verder kan ek spekuleer dat reeds gesorteer insette maak tak voorspeller skyn verwerker se maar raai byna al die takke korrek, wat sal verhoed dat pyplyn stalletjies.

Quick soort gemiddeld vereis ~ 1,38 N log N vergelykings. Dit maak nie baie baat by al gesorteer verskeidenheid in terme van vergelykings (maar dit doen in terme van swaps en waarskynlik in terme van tak voorspellings binne CPU).

My maatstawwe op redelik moderne verwerker toon die volgende:

Wanneer vergelyking funksie is 'n terugbel funksie (soos in qsort () LIBC implementering) quicksort is stadiger as mergesort met 15% op ewekansige insette en 30% vir al gesorteer verskeidenheid vir 64 bit heelgetalle.

Aan die ander kant, as vergelyking is nie 'n terugbel, my ondervinding is dat quicksort beter as mergesort met tot 25%.

Maar as jou (groot) opgestel het 'n paar unieke waardes, saam te smelt soort begin kry oor quicksort in elk geval.

Nou ja, miskien die bottom line is: as vergelyking is duur (bv terugbel funksie, vergelyk snare, vergelyk baie dele van 'n struktuur meestal kry om 'n tweede-derde-weer "as" om verskil te maak) - die kanse goed dat jy sal beter met merge soort wees. Vir eenvoudiger take sal quicksort vinniger wees.

Dit gesê al voorheen gesê dit is waarheid; - Quicksort kan wees N ^ 2, maar Sedgewick beweer dat 'n goeie ewekansige implementering het meer kanse van 'n rekenaar presterende soort word getref deur 'n weerlig as om te gaan N ^ 2 - Mergesort vereis ekstra ruimte

Wanneer ek eksperimenteer met beide sorteeralgoritmes, deur die tel van die aantal rekursiewe oproepe, quicksort het konsekwent minder rekursiewe oproepe as mergesort. Dit is as gevolg quicksort het spilpunte, en spilpunte is nie ingesluit in die volgende rekursiewe oproepe. Op dié manier quicksort kan rekursiewe basis geval bereik meer vinniger as mergesort.

Alle dinge gelyk, sou ek verwag dat die meeste mense om te gebruik wat ook al is die meeste gerieflik beskikbaar, en wat geneig is om te qsort (3). Anders as dit quicksort bekend baie vinnig op skikkings te wees, net soos mergesort is die algemene keuse vir lyste.

Wat ek wonder is hoekom dit so skaars om te sien radix of emmer soort. Hulle is O (n), ten minste op geskakelde lyste en al wat dit neem is 'n paar metode van die omskakeling van die sleutel tot 'n ordinale nommer. (Snare en dryf werk net fyn.)

Ek dink die rede het te doen met hoe rekenaarwetenskap geleer. Ek moes selfs my dosent in Algoritme ontleding aan te toon dat dit inderdaad moontlik is om vinniger as O sorteer (n teken (N)). (Hy het die bewys dat jy kan nie vergelyking soort vinniger as O (n teken (n)), wat waar is.)

In ander nuus, kan dryf word gesorteer as heelgetalle, maar jy moet die negatiewe getalle rondom daarna draai.

Edit: Eintlik, hier is 'n selfs meer bose manier om dryf-as-heelgetalle te sorteer: http: //www.stereopsis. com / radix.html . Let daarop dat die bietjie-daarby truuk, ongeag van wat sorteer algoritme jy eintlik gebruik kan word ...

Dit is moeilik om te ergste van MergeSort say.The is N (log2n) -n + 1, wat akkuraat as N gelyk 2 ^ k (Ek het hierdie reeds bewys) .En vir enige N, dis tussen (n LG N -. n + 1) en (n LG N + n + O (LG n)) Maar vir quickSort, sy beste is nlog2n (ook n gelyk 2 ^ k) .As jy verdeel Mergesort deur quickSort, dit is gelyk aan een wanneer n ' infinite.So dis asof die ergste geval van MergeSort is beter as die beste geval van quickSort, hoekom doen ons quicksort gebruik? Maar onthou, MergeSort is nie in plek is, is dit nodig 2n memeroy space.And MergeSort moet ook baie verskeidenheid afskrifte doen , wat ons nie sluit in die ontleding van algorithm.In n woord, MergeSort is regtig faseter as quicksort in theroy, maar in werklikheid wat jy nodig het om memeory ruimte oorweeg, die koste van verskeidenheid kopie, samesmelting is stadiger as 'n vinnige sort.I een keer het 'n eksperiment waar ek 1000000 syfers gegee in Java deur Random klas, en dit het 2610ms deur mergesort, 1370ms deur quicksort.

Klein toevoegings tot vinnige vs merge vorme.

Ook dit kan afhang van die soort van sortering items. Indien toegang tot items, ruil en vergelykings is nie eenvoudige operasies, soos vergelyk heelgetalle in vliegtuig geheue, dan saamsmelt soort kan beter algoritme wees.

Byvoorbeeld, ons sorteer items met behulp van netwerk protokol op afgeleë bediener.

Ook in persoonlike houers soos "gekoppel lys", die is geen voordeel van vinnige soort.
1. Merge soort op geskakelde lys, moenie bykomende geheue nodig het nie. 2. Toegang tot elemente in 'n vinnige soort is nie opeenvolgende (in geheue)

Quick soort is 'n in-place sorteer algoritme, sodat sy beter geskik vir skikkings. Saamsmelt soort aan die ander kant vereis ekstra stoorplek van O (N), en is meer geskik vir geskakelde lyste.

In teenstelling met skikkings, in hou lys wat ons kan items in die middel met O (1) ruimte en O (1) tyd, dus die merge operasie in merge soort geïmplementeer kan word sonder enige ekstra spasie. Maar die toekenning en de-toekenning ekstra ruimte vir skikkings het 'n nadelige uitwerking op die vlug tyd van merge soort. Saamsmelt soort gunste ook gekoppel lys as data is verkry agtermekaar, sonder veel ewekansige geheue toegang.

Quick soort aan die ander kant is 'n baie random geheue toegang en met 'n verskeidenheid kan ons direkte toegang tot die geheue sonder enige Dwarsbalke soos vereis deur geskakelde lyste. Ook vinnige soort wanneer dit gebruik word vir skikkings het 'n goeie ligging van verwysing as skikkings aansluitend in geheue gestoor word.

Hoewel beide sorteeralgoritmes gemiddelde kompleksiteit is O (NlogN), gewoonlik mense vir gewone take gebruik 'n verskeidenheid vir die stoor, en om dié rede 'n vinnige soort moet die algoritme van keuse te wees.

EDIT: Ek het nou net uitgevind dat saamsmelt soort ergste / beste / avg geval is altyd nlogn, maar 'n vinnige soort kan wissel van N2 (ergste geval wanneer elemente reeds gesorteer) om nlogn (avg / beste geval wanneer spilpunt altyd verdeel die verskeidenheid in twee helftes).

tyd en ruimte kompleksiteit Oorweeg beide. Vir Merge soort: Tyd kompleksiteit: O (nlogn), Ruimte kompleksiteit: O (nlogn)

Vir Quick soort: Tyd kompleksiteit: O (n ^ 2), Ruimte kompleksiteit: O (n)

Nou, hulle albei wen in elkeen scenerio. Maar, met behulp van 'n ewekansige spilpunt jy kan byna altyd te verminder Tyd kompleksiteit van Quick soort om O (nlogn).

So, Quick soort verkies in baie toepassings in plaas van Merge soort.

In C / C ++ land geneem toe nie die gebruik van STL houers, ek is geneig om quicksort gebruik, want dit is gebou in die aanloop tyd, terwyl mergesort is nie.

Ek glo dat in baie gevalle, dit is net die pad van minste weerstand.

Verder prestasie kan veel hoër met 'n vinnige soort wees, vir gevalle waar die hele dataset pas nie in die werk stel.

Een van die redes is meer filosofiese. Quicksort is Top> Down filosofie. Met n elemente uit te sorteer is daar n! moontlikhede. Met 2 afskortings van m & N-m wat onderling uitsluitend is, die aantal moontlikhede gaan af in verskeie ordes. m! * (N-m)! is kleiner deur verskeie bestellings as N! alleen. dink 5! vs 3! * 2 !. 5! het 10 keer meer moontlikhede as 2 mure van 2 & 3 elk. en ekstrapoleer tot 1 miljoen faktoriaal vs 900K! * 100K! teen So in plaas van om bekommerd te wees oor die stigting van 'n bevel in 'n reeks of 'n partisie, net vestig ten einde op 'n breër vlak in mure en verminder die moontlikhede binne 'n partisie. Enige vroeër gestig binne 'n verskeidenheid orde sal later versteur as die mure self is nie onderling uitsluitend.

Enige bottom-up orde benadering soos merge soort of hoop soort is soos 'n werkers of werknemer se benadering waar 'n mens begin te vergelyk op 'n mikroskopiese vlak vroeg. Maar hierdie orde is gebind om so gou verlore as 'n element in tussen hulle later op is gevind. Hierdie benaderings is baie stabiel en baie voorspelbaar, maar doen 'n sekere bedrag van ekstra werk.

Quick Sorteer is soos Bestuurs- benadering waar 'n mens is nie aanvanklik bekommerd oor 'n bevel, net oor die vergadering van 'n breë maatstaf met geen agting vir orde. Toe die mure is vernou totdat jy 'n gesorteerde stel kry. Die ware uitdaging in Quicksort is in die vind van 'n partisie of maatstaf in die donker wanneer jy weet niks van die elemente te sorteer. Dit is hoekom ons nie nodig het om 'n paar pogings om 'n mediaan waarde vind of kies 1 na willekeur of 'n arbitrêre "Bestuurs-" benadering te spandeer. Om 'n perfekte mediaan te vind kan beduidende hoeveelheid moeite en lei weer na 'n dom bottom-up benadering. So Quicksort sê net 'n pick n ewekansige spilpunt en hoop dat dit iewers in die middel sal wees of doen 'n paar werk om mediaan van 3, 5 of iets meer uit te vind om 'n beter mediaan te vind, maar nie van plan om volmaak te wees en nie te mors enige tyd in aanvanklik bestel. Dit lyk goed doen as jy gelukkig is of soms afbreek aan N ^ 2 as jy nie 'n mediaan te kry, maar net 'n kans te gee. Enigsins data is onvoorspelbaar. reg. So ek stem saam meer met die top -> af logiese benadering van quicksort & dit blyk dat die kans wat dit neem oor spilpunt seleksie & vergelykings wat dit vroeër spaar lyk beter werk meer kere as enige noukeurige & deeglike stabiele bodem -> up benadering soos saamsmelt soort. Maar

Gelisensieer onder: CC-BY-SA met toeskrywing

Nie verbonde aan StackOverflow