Kuten Yhdistä lajittelu, QuickSort on Divide and Conquer -algoritmi. Se valitsee elementin pivotiksi ja osioi annetun taulukon valitun pivotin ympärille. QuickSortista on monia eri versioita, jotka valitsevat pivotin eri tavoin.
- Valitse aina ensimmäinen elementti pivotiksi.
- Valitse aina viimeinen elementti pivotiksi (toteutettu alla)
- Valitse satunnainen elementti pivot-yksiköksi.
- Valitse mediaani pivotiksi.
QuickSortin avainprosessi on osio (). Osioiden kohteelle annetaan taulukoksi ja taulukon elementti x sarakkeeksi, x asetetaan oikeaan paikkaan lajiteltuihin matriiseihin ja kaikki pienemmät elementit (pienemmät kuin x) ennen x: tä ja kaikki suuremmat elementit (yli x) jälkeen x. Kaikki tämä on tehtävä lineaarisessa ajassa.
Pseudokoodi rekursiiviselle QuickSort-toiminnolle:
Osioalgoritmi
Osiota voidaan tehdä monella tavalla, näennäiskoodin jälkeen otetaan käyttöön CLRS-kirjassa annettu menetelmä. Logiikka on yksinkertainen, aloitamme vasemmanpuoleisesta elementistä ja pidämme kirjaa pienempien (tai yhtä suurien) elementtien indeksistä kuten i. Liikkumisen aikana, jos löydämme pienemmän elementin, vaihdamme nykyisen elementin arr: llä. Muussa tapauksessa ohitamme nykyisen elementin.
Osio (): n pseudokoodi
Osio (): n kuva:
Toteutus:
Seuraavassa on QuickSortin toteutukset:
Output:
Sorted array:1 5 7 8 9 10
QuickSort-analyysi
Aika, jonka QuickSort yleensä vie, voidaan kirjoittaa seuraavasti.
T(n) = T(k) + T(n-k-1) + (n)
Kaksi ensimmäistä termiä koskevat kahta rekursiivista kutsua, viimeinen termi on osiointiprosessi. k on elementtejä, jotka ovat pienempiä kuin pivot.
QuickSortin aika riippuu syötetaulukosta ja osiostrategiasta. Seuraavassa on kolme tapausta.
Pahin tapaus: Pahin tapaus tapahtuu, kun osioprosessi valitsee aina suurimman tai pienimmän elementin pivotiksi. Jos tarkastellaan edellä olevaa ositusstrategiaa, jossa viimeinen elementti valitaan aina pivotiksi, pahin tapaus tapahtuisi, kun matriisi on jo lajiteltu kasvavassa tai laskevassa järjestyksessä. Seuraavassa on toistuminen pahimmassa tapauksessa.
T(n) = T(0) + T(n-1) + (n)which is equivalent to T(n) = T(n-1) + (n)
Yllä olevan toistumisen ratkaisu on (n2).
Paras tapaus: Paras tapaus tapahtuu, kun osioprosessi valitsee aina keskielementti pivotina. Seuraava on toistuminen parhaassa tapauksessa.
T(n) = 2T(n/2) + (n)
Yllä olevan toistumisen ratkaisu on (nLogn). Se voidaan ratkaista päälauseen tapaus 2 avulla.
Keskimääräinen tapaus:
Keskimääräisen tapausanalyysin tekemiseksi meidän on otettava huomioon kaikki mahdolliset matriisin permutaatiot ja laskettava jokaisen permutaation aika, joka ei näyttää helpolta.
Voimme saada käsityksen keskimääräisestä tapauksesta tarkastelemalla tapausta, jossa osio asettaa O (n / 9) -elementit yhteen sarjaan ja O (9n / 10) -elementit toiseen sarjaan. Seuraava on tämän tapauksen toistuminen.
T(n) = T(n/9) + T(9n/10) + (n)
Yllä olevan toistumisen ratkaisu on myös O (nLogn)
Vaikka QuickSortin aika-aikakompleksi on pahinta, O (n2) on enemmän kuin monia muita lajittelualgoritmeja, kuten Yhdistä lajittelu ja Heap Lajittelu, QuickSort on käytännössä nopeampi, koska sen sisäinen silmukka voidaan toteuttaa tehokkaasti useimmissa arkkitehtuureissa ja useimmissa tosielämän tiedoissa. QuickSort voidaan toteuttaa eri tavoin muuttamalla pivot-valintaa niin, että pahin tapaus tapahtuu harvoin tietyntyyppisille tiedoille. Yhdistämislajittelua pidetään yleensä parempana, kun tietoja on paljon ja ne tallennetaan ulkoiseen muistiin.
Onko QuickSort vakaa?
Oletustoteutus ei ole vakaa. Mikä tahansa lajittelualgoritmi voidaan kuitenkin tehdä vakaana pitämällä indeksit vertailuparametrina.
Onko QuickSort paikallaan?
Paikallisten algoritmien laajan määritelmän mukaisesti se luokitellaan paikan päällä olevaksi lajittelualgoritmiksi, koska se käyttää ylimääräistä tilaa vain rekursiivisten toimintokutsujen tallentamiseen, mutta ei syötteen manipulointiin.
Kuinka QuickSort otetaan käyttöön linkitetyille luetteloille?
QuickSort yksittäisesti linkitetylle listalle
QuickSort kaksoislinkityssä luettelossa
Voimmeko ottaa QuickSortin käyttöön iteratiivisesti?
Kyllä, katso Iteratiivinen pikalajittelu.
Miksi pikalajittelu on MergeSortin sijaan matriisien lajittelussa
Nopea lajittelu on yleisessä muodossaan paikalla oleva lajittelu (ts. se ei vaadi ylimääräistä tallennustilaa), kun taas yhdistämislajittelu vaatii O (N) ylimääräistä tallennustilaa, N tarkoittaa taulukon kokoa, joka voi olla melko kallista. Yhdistämislajittelulle käytetyn ylimääräisen tilan varaaminen ja varaamisen poistaminen lisää algoritmin ajoaikaa. Verrattaessa keskimääräistä monimutkaisuutta havaitaan, että molemmilla tyypeillä on O (NlogN) keskimääräinen monimutkaisuus, mutta vakiot eroavat toisistaan. Matriisien kohdalla lajitteluhäviöt menevät ylimääräisen O (N) -tallennustilan käytöstä johtuen.
Useimmat Quick Lajittelun käytännön toteutukset käyttävät satunnaistettua versiota. Satunnaistettu versio on odottanut O: n (nLogn) ajan monimutkaisuutta.Pahin tapaus on mahdollista myös satunnaistetussa versiossa, mutta pahinta tapausta ei tapahdu tietylle mallille (kuten lajiteltu taulukko) ja satunnaistettu pikalajittelu toimii hyvin käytännössä.
Pikalajittelu on myös välimuistiin sopiva lajittelu algoritmi, koska sillä on hyvä viittauspaikka, kun sitä käytetään matriiseissa.
Nopea lajittelu on myös pyrstörekursiivinen, joten hännän puhelun optimointi tehdään.
Miksi MergeSort on suositeltava linkitettyjen luetteloiden QuickSortin sijaan ?
Linkitettyjen luetteloiden tapauksessa tapaus on erilainen pääasiassa matriisien ja linkitettyjen luetteloiden muistin allokoinnin erojen vuoksi. Toisin kuin taulukot, linkitetyt luettelosolmut eivät välttämättä ole muistissa. Toisin kuin taulukko, linkitetyssä luettelossa voimme lisätä kohteita keskelle O (1) ylimääräiseen tilaan ja O (1) -aikaan. Siksi yhdistämislajittelutoiminto voidaan toteuttaa ilman ylimääräistä tilaa linkitetyille luetteloille.
Taulukoissa voimme tehdä satunnaiskäytön, koska elementit ovat jatkuvia muistissa. Sanotaan, että meillä on kokonaisluku (4-tavuinen) taulukko A ja anna A: n osoitteen olla x, jolloin pääset A: han, voimme käyttää suoraan muistia kohdassa (x + i * 4). Toisin kuin taulukot, emme voi tehdä satunnaista linkitettyä linkitettyä luetteloa. Pikalajittelu vaatii paljon tällaista käyttöä. Linkitetyssä luettelossa pääsemme i: n hakemistoon meidän on matkustettava jokainen solmu pään päästä toiseen solmuun, koska meillä ei ole jatkuvaa muistilohkoa. Siksi yleiskustannukset kasvavat nopeaa lajittelua varten. Yhdistä lajittelu käyttää tietoja peräkkäin ja satunnaiskäytön tarve on pieni.
Kuinka QuickSort optimoidaan niin, että se vie O (Log n) lisätilaa pahimmassa tapauksessa?
Katso QuickSort Tail Call Optimization (Pienimmän tapauksen pienentäminen Log n: ksi)
Yksittäiskuvat:
- Tietokilpailu QuickSortista
- Viimeisimmät artikkelit QuickSortista
- Koodaaminen lajittelu.
Muut GeeksforGeeksin / GeeksQuizin lajittelualgoritmit:
valintalajittelu, kuplalajittelu, lisäyslajittelu, yhdistämislajittelu, kasan lajittelu, pikalajittelu , Radix-lajittelu, laskulajittelu, kauhalajittelu, ShellSort, kampa-lajittelu, kyyhkysreiän lajittelu