Mõlemad sorteerimistehnikad, kiire sorteerimine ja ühendamine on üles ehitatud jagamis- ja vallutamismeetodile, kus elementide kogum on jagatud ja seejärel kombineeritud pärast ümberkorraldamist. Kiire sorteerimine nõuab tavaliselt rohkem võrdlusi kui suurte elementide kogumise sortimiseks.
Võrdluskaart
| Võrdluse alus | Kiire sortimine | Ühenda sort |
|---|---|---|
| Massiivi elementide jaotamine | Elementide nimekirja jagamine ei ole tingimata pooleks jagatud. | Array jagatakse alati pooleks (n / 2). |
| Halvim juhtum | O (n2) | O (n log n) |
| Töötab hästi | Väiksem massiiv | Töötab trahvi mis tahes massiivi puhul. |
| Kiirus | Väiksemate andmekogumite jaoks on kiirem kui muud sorteerimisalgoritmid. | Järjepidev kiirus igasugustes andmekogumites. |
| Täiendav ruumi nõudmine | Vähem | Veel |
| Tõhusus | Ebaefektiivne suuremate massiividega. | Tõhusam. |
| Sorteerimismeetod | Sisemine | Väline |
Kiire sorteerimise mõiste
Kiire sorteerimine on laialt levinud sorteerimisalgoritmi abil, kuna see on lühike massiivide jaoks kiire. Elementide kogum jagatakse korduvalt osadeks, kuni seda pole võimalik jagada. Kiire sorteerimine on tuntud ka kui partitsioonivahetus . See kasutab elementide jagamiseks võtmeelementi (nn pivot). Üks partitsioon sisaldab neid elemente, mis on võtmeelemendist väiksemad. Teine partitsioon sisaldab neid elemente, mis on põhielemendist suuremad. Elemendid sorteeritakse rekursiivselt.
Oletame, et A on massiivi A [1], A [2], A [3], …… .., A [n] n numbrit, mis tuleb sorteerida. Kiire sorteerimise algoritm koosneb järgmistest sammudest.
- Võtmeks valitud esimene element või suvaline element eeldab võtit = A (1).
- "Madal" osuti asetatakse teise ja "üles" kursor asetatakse massiivi viimasele elemendile, st madal = 2 ja üles = n;
- Järjekindlalt suurendage "madala" kursorit ühe asendi võrra, kuni (A [low]>> klahv).
- Pidevalt tõstke ülespoole suunatud kursorit ühe asendi võrra, kuni (A [üles] <= klahv).
- Kui üles tõus on suurem kui madal vahetus A [madal] ja A [üles].
- Korrake sammu 3, 4 ja 5, kuni etapis 5 esinev tingimus ebaõnnestub (st ülespoole <= madal) ja vahetage A [üles] klahviga.
- Kui võtmest vasakul olevad elemendid on võtmest väiksemad ja võtme paremad elemendid on võtmest suuremad, jagatakse massiiv kaheks alammassiks.
- Ülaltoodud protseduuri rakendatakse korduvalt alaregioonidele, kuni kogu massiiv on sorteeritud.
Eelised ja puudused
Sellel on hea keskmine juhtumikäitumine. Kiire sorteerimise keerukus on hea, see tähendab, et see on kiirem kui algoritmid nagu mullide sortimine, sisestamise sorteerimine ja valik. Siiski on see keeruline ja väga rekursiivne, see on põhjus, miks see ei sobi suurte massiivide jaoks.
Merge Sort'i määratlus
Ühendamise sort on väline algoritm, mis põhineb ka jagamis- ja vallutamisstrateegial. Elemendid jagatakse alammassiks (n / 2) ikka ja jälle, kuni jääb alles üks element, mis oluliselt vähendab sortimisaega. See kasutab täiendavat salvestust abisüsteemi salvestamiseks. Liigu sortimine kasutab kolme massiivi, kus kahte kasutatakse iga poole salvestamiseks, ja kolmandat kasutatakse lõpliku sorteeritud nimekirja salvestamiseks. Seejärel sorteeritakse iga massiiv rekursiivselt. Lõpuks ühendatakse alarühmad, et muuta see massi n elemendi suuruseks. Nimekiri jaguneb alati vaid pooleks (n / 2), mis on erinev kiireks sortimiseks.
Olgu A sorteeritavate elementide arv A [1], A [2], ………, A [n]. Ühendamise sort järgib antud samme.
- Jagage massiivi A umbes n / 2-ga sorteeritud alammaatriksiks 2, mis tähendab, et elemendid (A [1], A [2]), (A [3], A [4]), (A [3]) k], A [k + 1]) (A [n-1], A [n]) alammaatriksid peavad olema sorteeritud järjekorras.
- Ühendage iga paari paari, et saada kokku sorteeritud alarühmade nimekiri, mille suurus on 4; alarubade elemendid on samuti sorteeritud, (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]).
- Etapp 2 viiakse korduvalt läbi seni, kuni on olemas ainult üks sorteeritud massiiv, mille suurus on n.
Eelised ja puudused
Ühendamise sorteerimise algoritm toimib täpselt samamoodi, hoolimata sortimisega seotud elementide arvust. See toimib ka suurte andmekogumite korral. Siiski tarbib see suuremat osa mälust.
Kiire sorteerimise ja ühendamise sorteerimise peamised erinevused
- Ühendamise sorteerimisel tuleb massiiv jaotada vaid kaheks pooleks (st n / 2). Kiirelt sorteeritult ei ole mingit sundi nimekirja jagamine võrdseteks elementideks.
- Kiire sorteerimise kõige halvem keerukus on O (n2), kuna see võtab halvemas olukorras palju rohkem võrdlusi. Seevastu kombineerimisel on sama halvim ja keskmine juhtumite keerukus, see on O (n log n).
- Merge sort võib toimida mis tahes tüüpi andmekogumites, kas see on suur või väike. Vastupidi, kiire sorteerimine ei suuda suurte andmekogumitega hästi töötada.
- Kiire sorteerimine on mõnel juhul kiirem kui ühendamine, näiteks väikeste andmekogumite puhul.
- Liidetüüp nõuab täiendavate mäluruumide lisandmoodulite salvestamiseks. Teisest küljest ei vaja kiire sorteerimine lisaruumi jaoks palju ruumi.
- Liigu sort on efektiivsem kui kiire sorteerimine.
- Kiire sorteerimine on sisemine sorteerimise meetod, kus sorteeritavad andmed korrigeeritakse korraga põhimälus. Vastupidi, ühendamise sort on väline sortimismeetod, kus sorteeritavaid andmeid ei saa mällu üheaegselt paigutada ja mõnda tuleb hoida lisamälus.
Järeldus
Kiire sorteerimine on kiirem juhtum, kuid mõnes olukorras on see ebaefektiivne ning võrdleb palju ka võrdlusi. Kuigi ühendamise sort nõuab vähem võrdlust, vajab see täiendava mäluruumi 0 (n) lisarea salvestamiseks, samas kui kiire sortimine vajab ruumi O (log n).
