Sisältö

• Vertailutaulukko
• Määritelmä Quick Sort
• Määritelmä Yhdistä lajittelu
• johtopäätös

Pikalajittelu- ja yhdistämisalgoritmit perustuvat jakamis- ja valloitusalgoritmiin, joka toimii melko samalla tavalla. Aikaisempi ero nopean ja yhdistävän lajittelun välillä on, että pikalajittelussa lajitteluun käytetään kääntöelementtiä. Toisaalta yhdistämislajittelu ei käytä kääntöelementtiä lajitteluun.

Sekä lajittelutekniikat, nopea lajittelu ja yhdistäminen lajitellaan jakamis- ja valloitusmenetelmällä, jossa elementtijoukot erotetaan ja yhdistetään sitten uudelleenjärjestelyn jälkeen. Pikalajittelu vaatii yleensä enemmän vertailuja kuin yhdistämislajittelu suuren elementtijoukon lajittelua varten.

1. 1. Vertailutaulukko
   2. Määritelmä
   3. Keskeiset erot
   4. johtopäätös

Vertailutaulukko

Vertailun perusteet	Nopea lajittelu	Yhdistä lajittelu
Elementtien osiointi taulukossa	Elementtiluettelon jakamista ei välttämättä jaeta kahteen osaan.	Matriisi on aina jaettu kahteen osaan (n / 2).
Pahimman tapauksen monimutkaisuus	Päällä2)	O (n log n)
Toimii hyvin	Pienempi joukko	Toimii hyvin minkä tahansa tyyppisissä ryhmissä.
Nopeus	Nopeampi kuin muut pienen tietojoukon lajittelualgoritmit.	Tasainen nopeus kaikentyyppisissä tietokokonaisuuksissa.
Lisävarastotila	Vähemmän	Lisää
tehokkuus	Tehokas suurten ryhmien kanssa.	Tehokkaampi.
Lajittelutapa	sisäinen	ulkoinen

Määritelmä Quick Sort

Nopea lajittelu on yleisesti käytetty lajittelualgoritmi, koska se on nopea lyhyille ryhmille. Elementtijoukko on jaettu toistuvasti osiin, kunnes sitä ei ole mahdollista jakaa edelleen. Pikalajittelu tunnetaan myös nimellä osiot vaihto lajittelu. Se käyttää avainelementtiä (tunnetaan nivelnä) osien jakamiseen. Yksi osio sisältää ne elementit, jotka ovat pienempiä kuin avainelementti. Toinen osio sisältää ne elementit, jotka ovat suurempia kuin avainelementti. Elementit lajitellaan rekursiivisesti.

Oletetaan, että A on taulukko A, A, A, …… .., A, joka on n-numero ja jotka on lajiteltava. Pikalajittelualgoritmi koostui seuraavista vaiheista.

1. Ensimmäinen elementti tai mikä tahansa avaimeksi valittu satunnainen elementti, oletetaan avain = A (1).
2. "Matala" osoitin sijoitetaan toiseen ja "ylös" osoitin taulukon viimeiseen elementtiin, ts. Matala = 2 ja ylös = n;
3. Lisää johdonmukaisesti "matalaa" osoitinta yhdellä paikalla, kunnes (A> -näppäin).
4. Pienennä osoitinta “ylöspäin” jatkuvasti yhdellä paikalla, kunnes (A <= näppäin).
5. Jos ylöspäin on suurempi kuin alhainen vaihto A A: n kanssa.
6. Toista vaiheet 3,4 ja 5, kunnes vaiheen 5 ehto epäonnistuu (ts. Ylöspäin = = matala), sitten vaihda A avaimen kanssa.
7. Jos näppäimen vasemmat elementit ovat pienempiä kuin näppäin ja näppäimen oikealla puolella olevat elementit ovat suurempia kuin avain, niin taulukko jaetaan kahteen alaryhmään.
8. Edellä mainittua menettelytapaa sovelletaan toistuvasti alaryhmiin, kunnes koko taulukko on lajiteltu.

   

   
   

Hyödyt ja haitat

Sillä on hyvä keskimääräinen tapauskäyttäytyminen. Pikalajittelun ajoaika on monimutkainen, joten se on nopeampi kuin algoritmit, kuten kuplalajittelu, lisäyslaji ja valintalaji. Se on kuitenkin monimutkainen ja hyvin rekursiivinen, ja tästä syystä se ei sovellu suurille ryhmille.

Määritelmä Yhdistä lajittelu

Yhdistä lajittelu on ulkoinen algoritmi, joka perustuu myös jakaa ja valloita -strategiaan. Elementit jaetaan uudelleen ja uudelleen alaryhmiin (n / 2), kunnes jäljellä on vain yksi elementti, mikä vähentää merkittävästi lajitteluaikaa. Se käyttää ylimääräistä tallennustilaa lisäryhmän tallentamiseen. Yhdistämislajittelu käyttää kolmea taulukkoa, joissa kahta käytetään kunkin puolikkaan tallentamiseen, ja kolmatta käytetään lopullisen lajiteltujen luetteloiden tallentamiseen. Kukin taulukko lajitellaan sitten rekursiivisesti. Vihdoin alaryhmät yhdistetään, jotta siitä muodostuisi taulukon n elementtikoko. Lista on aina jaettu vain puoleen (n / 2), jotka eroavat nopeaan lajitteluun.

Olkoon A joukko n lukumäärää lajiteltavia elementtejä A, A, ………, A. Yhdistämislajittelu seuraa annettuja vaiheita.

1. Jaa taulukko A noin n / 2 lajiteltuun alajoukkoon 2: lla, mikä tarkoittaa, että (A, A), (A, A), (A, A), (A, A) -alamatriisien elementtien on oltava olla järjestäytyneessä järjestyksessä.
2. Yhdistä jokainen paripari saadaksesi luettelon lajitelluista alaryhmistä, joiden koko on 4; myös alaryhmien elementit ovat lajiteltuina järjestyksessä (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Vaihe 2 suoritetaan toistuvasti, kunnes on vain yksi lajiteltu ryhmä, jonka koko on n.

   

Hyödyt ja haitat

Yhdistämisjärjestysalgoritmi suoritetaan täsmälleen samalla tavalla ja tarkasti lajittelussa mukana olevien elementtien lukumäärästä riippumatta. Se toimii hyvin jopa suuren tietojoukon kanssa. Se kuluttaa kuitenkin suuremman osan muistista.

1. Yhdistelmälajittelussa taulukko on jaettava vain kahteen puolikkaaseen (ts. N / 2). Toisin kuin nopeassa lajittelussa, ei ole pakko jakaa luetteloa yhtäläisiksi elementeiksi.
2. Pahimmassa tapauksessa nopean lajittelun monimutkaisuus on O (n²), koska se vie paljon enemmän vertailuja pahimmassa kunnossa. Sitä vastoin yhdistelmälajittelulla on sama pahin tapaus ja keskimääräinen tapauksen monimutkaisuus, eli O (n log n).
3. Yhdistelmälajittelu voi toimia hyvin minkä tahansa tyyppisissä tietokokonaisuuksissa, olivatpa ne sitten suuria vai pieniä. Päinvastoin, nopea lajittelu ei voi toimia hyvin suurten tietojoukkojen kanssa.
4. Nopea lajittelu on joissain tapauksissa nopeampaa kuin yhdistämislajittelu, esimerkiksi pienissä tietojoukoissa.
5. Yhdistämislajittelu vaatii lisämuistitilaa apurakettien tallentamiseksi. Toisaalta nopea lajittelu ei vaadi paljon tilaa ylimääräistä tallennustilaa varten.
6. Yhdistäminen on tehokkaampaa kuin nopea lajittelu.
7. Pikalajittelu on sisäinen lajittelumenetelmä, jossa lajiteltavaa tietoa säädetään kerrallaan päämuistissa. Yhdistämislajittelu on sitä vastoin ulkoinen lajittelumenetelmä, jossa lajiteltavaa tietoa ei voida sijoittaa muistiin samanaikaisesti ja osa on pidettävä apumuistissa.

johtopäätös

Nopea lajittelu on nopeampia tapauksia, mutta on tehoton tietyissä tilanteissa ja suorittaa myös paljon vertailuja yhdistettyyn lajitteluun verrattuna. Vaikka yhdistämislajittelu vaatii vähemmän vertailua, se tarvitsee ylimääräisen muistitilan 0 (n) ylimääräisen taulukon tallentamiseksi, kun taas nopea lajittelu tarvitsee tilaa O (log n).