Sisu

• Võrdlusdiagramm
• Kiire sortimise määratlus
• Liitmise sortimise määratlus
• Järeldus

Kiire sortimise ja liitmise algoritmid põhinevad jagamise ja vallutamise algoritmil, mis töötab üsna sarnaselt. Varasem erinevus kiir- ja ühendamissorteerimise vahel on see, et kiirsorteerimisel kasutatakse sorteerimiseks pöördeelementi. Teisest küljest ei kasuta liitmise sortimine sorteerimiseks pivot-elementi.

Mõlemad sorteerimistehnikad, kiire sorteerimine ja liitmine sorteeritakse üles jagamise ja vallutamise meetodil, mille käigus elementide komplekt jagatakse osadeks ja ühendatakse seejärel pärast ümberkorraldamist. Kiire sortimine nõuab suure hulga elementide sorteerimiseks tavaliselt rohkem võrdlusi kui merge sortimine.

1. 1. Võrdlusdiagramm
   2. Definitsioon
   3. Peamised erinevused
   4. Järeldus

Võrdlusdiagramm

Võrdluse alus	Kiire sortimine	Ühenda sorteerimine
Elementide jaotamine massiivis	Elementide loendi jagamine ei ole tingimata jagatud pooleks.	Massiiv jagatakse alati pooleks (n / 2).
Halvim juhtumite keerukus	Peal2)	O (n log n)
Toimib hästi	Väiksem massiiv	Toimib hästi igat tüüpi massiivides.
Kiirus	Kiirem kui muud väikese andmekogumi sortimisalgoritmid.	Ühtlane kiirus igat tüüpi andmekogumites.
Täiendav hoiuruumi nõue	Vähem	Veel
Tõhusus	Ebaefektiivne suuremate massiivide korral.	Tõhusam.
Sorteerimismeetod	Sisemine	Väline

Kiire sortimise määratlus

Kiire sortimine on üldlevinud sortimisalgoritm, kuna see on lühikeste massiivide jaoks kiire. Elementide komplekt jaguneb korduvalt osadeks, kuni seda pole enam võimalik jagada. Kiiret sortimist nimetatakse ka partitsioonide vahetamise sort. Elementide eraldamiseks kasutab see võtmeelementi (nn pöördepunkti). Üks partitsioon sisaldab neid elemente, mis on võtmeelemendist väiksemad. Teine partitsioon sisaldab neid elemente, mis on võtmeelemendist suuremad. Elemendid sorteeritakse rekursiivselt.

Oletame, et A on massiiv A, A, A, …… .., A n arvust, mis tuleb sortida. Kiire sortimise algoritm koosnes järgmistest sammudest.

1. Esimene element või võtmeks valitud suvaline element eeldatakse, et võti = A (1).
2. "Madal" osuti asetatakse teisele ja "üles" osuti massiivi viimasele elemendile, st madal = 2 ja üles = n;
3. Järk-järgult suurendage "madalat" osutit ühe positsiooni võrra kuni (A> klahv).
4. Vähendage osutit “üles” pidevalt ühe asendi võrra, kuni (A <= klahv).
5. Kui üles on suurem kui madal vahetus A A-ga.
6. Korrake samme 3,4 ja 5, kuni etapis 5 esitatud tingimus ebaõnnestub (st üles <= madal), seejärel vahetage A võtmega.
7. Kui võtmest vasakpoolsed elemendid on võtmest väiksemad ja võtme parempoolsed elemendid on võtmest suuremad, jaotatakse massiiv kaheks alammassiiviks.
8. Ülaltoodud protseduuri rakendatakse alammassiividele korduvalt, kuni kogu massiiv on sorteeritud.

   

   
   

Eelised ja puudused

Selle juhtumikäitumine on hea. Kiire sortimise käitamisaeg on keeruline, st see on kiirem kui sellised algoritmid nagu mullide sortimine, sisestamise sortimine ja valiku sortimine. Kuid see on keeruline ja väga rekursiivne, mistõttu see ei sobi suurte massiivide jaoks.

Liitmise sortimise määratlus

Ühenda sorteerimine on väline algoritm, mis põhineb ka jagamise ja vallutamise strateegial. Elemendid jaotatakse ikka ja jälle alamassiivideks (n / 2), kuni järele on jäänud ainult üks element, mis lühendab sorteerimisaega märkimisväärselt. See kasutab abimassiivi salvestamiseks täiendavat salvestusruumi. Ühenda sortimisel kasutatakse kolme massiivi, kus kummagi poole salvestamiseks kasutatakse kahte ja kolmandat sorteeritakse lõplikku sorteeritud nimekirja. Seejärel sorteeritakse iga massiiv rekursiivselt. Lõpuks liidetakse alamkihid massiivi elemendi suuruseks. Loend jaguneb alati vaid pooleks (n / 2), mis erinevad kiire sortimise osas.

Olgu A sorteeritavate elementide n hulga massiiv A, A, ………, A. Ühendamise sort järgib antud samme.

1. Jagage massiiv A umbes n / 2 järjestatud alammassiiviks 2-ga, mis tähendab, et alammassiivide (A, A), (A, A), (A, A), (A, A) elemendid peavad olema järjestatud järjekorras.
2. Kombineerige iga paaripaar, et saada sorteeritud alamkihtide suurus 4; ka alamkihtide elemendid on järjestatud järjekorras (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. 2. sammu korratakse korduvalt, kuni leidub ainult üks sorteeritud massiiv suurusega n.

   

Eelised ja puudused

Ühendamisalgoritm töötab täpselt samal viisil ja täpselt, sõltumata sorteerimisse kaasatud elementide arvust. See töötab hästi isegi suure andmekogumi korral. Kuid see tarbib suuremat osa mälust.

1. Ühendamis sorteerimisel tuleb massiiv jagada vaid kaheks pooleks (st n / 2). Vastupidiselt sellele ei ole kiire sorteerimise korral sunnitud nimekirja jagama võrdseteks elementideks.
2. Halvimal juhul on kiire sortimise keerukus O (n²), kuna kõige halvemas seisukorras on vaja võtta palju rohkem võrdlusi. Seevastu ühendamisjärjekordadel on sama halvim ja keskmise juhtumi keerukus, st O (n log n).
3. Ühendamise sort saab hästi töötada igat tüüpi andmekogumitega, olgu need suured või väikesed. Vastupidi, kiire sortimine ei saa suurte andmekogude korral hästi hakkama.
4. Kiire sortimine on mõnel juhul kiirem kui liitmine, näiteks väikeste andmekogumite korral.
5. Ühenda sorteerimine nõuab lisamassiivide salvestamiseks lisamälu. Teisest küljest ei vaja kiire sortimine palju ruumi täiendava salvestusruumi jaoks.
6. Ühendamine on tõhusam kui kiire sortimine.
7. Kiire sortimine on sisemine sortimisviis, kus sorteeritavaid andmeid kohandatakse põhimälus korraga. Ühendamis sortimine on vastupidiselt väline sortimismeetod, kus sorteeritavaid andmeid ei saa korraga mällu mahutada ja osa tuleb hoida lisamälus.

Järeldus

Kiire sortimine on kiiremad juhtumid, kuid on mõnes olukorras ebaefektiivne ja teeb ka palju võrdlusi, võrreldes ühendatud sortimisega. Ehkki ühendamis sortimine nõuab vähem võrdlust, vajab see täiendava massiivi salvestamiseks täiendavat mäluruumi 0 (n), samas kui kiire sortimine vajab ruumi O (log n).