Suositeltava, 2024

Toimituksen Valinta

Pika-lajittelun ja yhdistämisen lajittelun välinen ero

Nopea lajittelu- ja yhdistämisalgoritmit perustuvat jakautumis- ja valloitusalgoritmiin, joka toimii aivan samankaltaisella tavalla. Aikaisempi ero nopean ja yhdistävän lajittelun välillä on, että pikajärjestyksessä käytetään kääntöelementtiä lajitteluun. Toisaalta yhdistämislaji ei käytä kääntöelementtiä lajittelun suorittamiseen.

Sekä lajittelutekniikat, nopea lajittelu ja yhdistäminen lajitellaan jaetaan ja valloitetaan -menetelmällä, jossa elementtiryhmä on jaettu ja yhdistetty uudelleen järjestelyn jälkeen. Nopea lajittelu vaatii yleensä enemmän vertailuja kuin yhdistää lajittelu suuren joukon elementtejä varten.

Vertailukaavio

Vertailun perusteetNopea lajitteluYhdistä lajittelu
Ryhmän elementtien jakaminenElementtien luettelon jakaminen ei välttämättä ole jaettu puoleen.Array on aina jaettu puoleen (n / 2).
Pahimmassa tapauksessa monimutkaisuusO (n2)O (n log n)
Toimii hyvinPienempi ryhmäToimii hienosti missä tahansa ryhmässä.
NopeusNopeampi kuin muut lajittelualgoritmit pienille tietosarjoille.Johdonmukainen nopeus kaikentyyppisissä tietosarjoissa.
Muita varastotilavaatimuksiaVähemmänLisää
tehokkuusEi tehokasta suuremmille ryhmille.Tehokkaampi.
Lajittelumenetelmäsisäinenulkoinen

Määritelmä Quick Sort

Nopeaa lajittelua käytetään laajasti lajittelualgoritmilla, koska se on nopea lyhyille matriiseille. Elementtien joukko on jaettu osiin toistuvasti, kunnes sitä ei ole mahdollista jakaa edelleen. Nopea lajittelu tunnetaan myös osionvaihdon lajitteluna . Se käyttää avainelementtiä (ns. Pivot) elementtien 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 joukko A [1], A [2], A [3], …… .., A [n] n lukumäärä, jotka on lajiteltava. Nopea lajittelualgoritmi koostuu seuraavista vaiheista.

  1. Ensimmäinen elementti tai jokin satunnaiselementti, joka on valittu avaimeksi, olettaa avaimen = A (1).
  2. "Alhainen" osoitin sijoitetaan toiseen ja "ylös" osoitin sijoitetaan taulukon viimeiseen elementtiin eli matala = 2 ja ylös = n;
  3. Nosta johdonmukaisesti ”matala” osoitinta yhdellä asennolla, kunnes (A [pieni]> -näppäin).
  4. Vähennä jatkuvasti ylöspäin osoittavaa osoitinta yhdellä asennolla, kunnes (A [ylös] <= avain).
  5. Jos ylöspäin on suurempi kuin alhainen vaihto A [alhainen] A [ylös].
  6. Toista vaihe 3, 4 ja 5, kunnes vaiheen 5 ehto epäonnistuu (eli <<matala) ja vaihda sitten A [ylös] näppäimellä.
  7. Jos avaimen vasemmalla olevat elementit ovat pienempiä kuin avain ja avaimen oikeat elementit ovat suurempia kuin avain, niin massiivi jaetaan kahteen aliryhmään.
  8. Edellä kuvattua menettelyä sovelletaan toistuvasti alarajoihin, kunnes koko taulukko on lajiteltu.

Hyödyt ja haitat

Siinä on hyvä keskimääräinen tapauskäyttäytyminen. Nopean lajittelun ajoaikojen monimutkaisuus on hyvä, eli se on nopeampi kuin algoritmit, kuten kupla lajittelu, lisäyksen lajittelu ja valinta. Se on kuitenkin monimutkainen ja hyvin rekursiivinen, siksi se ei sovellu suuriin ryhmiin.

Määrittele yhdistäminen

Yhdistä lajittelu on ulkoinen algoritmi, joka perustuu myös jakamis- ja valloitusstrategiaan. Elementit jaetaan aliryhmiin (n / 2) uudelleen ja uudelleen, kunnes vain yksi elementti jää jäljelle, mikä vähentää merkittävästi lajitteluaikaa. Se käyttää ylimääräistä tallennustilaa apurivin tallentamiseen. Yhdistämisen lajittelussa käytetään kolmea taulukkoa, joista kaksi käytetään kunkin puolen tallentamiseen, ja kolmas käytetään lopullisen lajitellun luettelon tallentamiseen. Jokainen taulukko lajitellaan sitten rekursiivisesti. Lopuksi alaryhmät yhdistetään siten, että se on n elementin koko. Lista on aina jaettu vain puoleen (n / 2), joka ei ole sama kuin nopea lajittelu.

Olkoon A joukko lajiteltavia n lukumäärää A [1], A [2], ………, A [n]. Yhdistystyyppi seuraa annettuja vaiheita.

  1. Jaa matriisi A noin n / 2-lajiteltuun aliryhmään 2: lla, mikä tarkoittaa, että elementit (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]) (A [n-1], A [n]) aliryhmien on oltava lajiteltuja.
  2. Yhdistä kukin paripari saadaksesi luettelon lajitelluista alaryhmistä, joiden koko on 4; alaryhmien elementit ovat myös lajitellussa järjestyksessä (A [1], A [2], A [3], A [4], ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……, (A [n-3], A [n-2], A [n-1], A [n]).
  3. Vaihe 2 suoritetaan toistuvasti, kunnes on vain yksi lajiteltu ryhmä, jonka koko on n.

Hyödyt ja haitat

Yhdistämislajialgoritmi toimii täsmälleen samalla ja tarkalla tavalla lajitteluun liittyvien elementtien lukumäärästä riippumatta. Se toimii hyvin myös suurella tietosarjalla. Se kuluttaa kuitenkin suurempaa osaa muistista.

Pikavalinnan ja yhdistämisen lajittelun keskeiset erot

  1. Yhdistämisjärjestyksessä matriisi on jaettava vain kahteen puolikkaaseen (eli n / 2). Niin kuin nopeassa järjestyksessä, ei ole pakko jakaa lista tasa-arvoisiin osiin.
  2. Nopean lajittelun pahin tapa on O (n2), koska se vie paljon enemmän vertailuja pahimmassa kunnossa. Sitä vastoin yhdistämislajilla on sama pahin tapaus ja keskimääräiset tapauskompleksit, eli O (n log n).
  3. Yhdistämisen lajittelu voi toimia hyvin kaikentyyppisissä tietosarjoissa, olipa se suuri tai pieni. Nopea lajittelu ei päinvastoin toimi hyvin suurten tietokokonaisuuksien kanssa.
  4. Nopea lajittelu on joissakin tapauksissa nopeampaa kuin yhdistää lajittelu, kuten pienissä tietosarjoissa.
  5. Yhdistä lajittelu edellyttää ylimääräistä muistitilaa apujärjestelmien tallentamiseen. Toisaalta nopea lajittelu ei vaadi paljon tilaa lisäsäilytykseen.
  6. Yhdistä lajittelu on tehokkaampaa kuin nopea lajittelu.
  7. Nopea lajittelu on sisäinen lajittelutapa, jossa lajiteltavat tiedot säädetään kerralla päämuistissa. Toisaalta yhdistämislaji on ulkoinen lajittelumenetelmä, jossa lajiteltavaa dataa ei voida sijoittaa muistiin samanaikaisesti, ja jotkut on pidettävä apumuistissa.

johtopäätös

Nopea lajittelu on nopeampia tapauksia, mutta se on tehoton joissakin tilanteissa ja tekee myös paljon vertailuja verrattuna lajitteluun. Vaikka yhdistämislaji vaatii vähemmän vertailua, se tarvitsee lisämuistin 0 (n) ylimääräisen taulukon tallentamiseksi, kun taas nopea lajittelu vaatii tilaa O: sta (log n).

Top