Abi rūšiavimo technikos, greitas rūšiavimas ir susiliejimas yra sukonstruoti pagal pasidalijimo ir užkariavimo metodą, kuriame elementų rinkinys yra suskirstytas ir po to sujungiamas po pertvarkymo. Greitai surūšiuoti paprastai reikia daugiau palyginimų, nei sujungti, kad surūšiuoti didelį elementų rinkinį.
Palyginimo diagrama
| Palyginimo pagrindas | Greitas rūšiavimas | Sujungti rūšiuoti |
|---|---|---|
| Masyvo elementų pasiskirstymas | Elementų sąrašo dalijimas nebūtinai padalijamas į pusę. | Array visada skirstoma į pusę (n / 2). |
| Blogiausio atvejo sudėtingumas | O (n2) | O (n log n) |
| Veikia gerai | Mažesnis masyvas | Veikia bauda bet kokio tipo masyvuose. |
| Greitis | Greičiau nei kiti rūšiavimo algoritmai mažiems duomenų rinkiniams. | Nuoseklus greitis visų tipų duomenų rinkiniuose. |
| Papildomas saugojimo vietos reikalavimas | Mažiau | Daugiau |
| Efektyvumas | Neefektyvus didesnėms matricoms. | Efektyvesnis. |
| Rūšiavimo metodas | Vidinis | Išorinis |
„Quick Sort“ apibrėžimas
Greitas rūšiavimas yra visapusiškai naudojamas rūšiavimo algoritmu, nes jis yra trumpas trumpoms matricoms. Elementų rinkinys pakartotinai suskirstytas į dalis, kol jo nebegalima dalyti. Greitas rūšiavimas taip pat žinomas kaip pertvarų keitimas . Jis naudoja pagrindinį elementą (vadinamą posūkiu) elementų skaidymui. Viename skaidinyje yra tie elementai, kurie yra mažesni už pagrindinį elementą. Kitame skirsnyje yra tie elementai, kurie yra didesni už pagrindinį elementą. Elementai yra rūšiuojami rekursyviai.
Tarkime, A yra masyvas A [1], A [2], A [3], …… .., A [n] n skaičius, kurį reikia surūšiuoti. Greitas rūšiavimo algoritmas susideda iš šių žingsnių.
- Pirmasis elementas arba atsitiktinis elementas, pasirinktas kaip raktas, prisiima raktą = A (1).
- „Žemas“ rodyklė yra antrajame, o „aukštyn“ rodyklė yra paskutiniame masyvo elemente, ty žemas = 2 ir aukštesnis = n;
- Nuosekliai didinkite „žemą“ rodiklį vienoje padėtyje, kol (A [žemas]> klavišas).
- Nuolat, sumažinkite rodyklę „aukštyn“ vienu padėčiu, kol (A [aukštyn] <= raktas).
- Jei aukštyn yra didesnis nei mažas A [žemas] su A [aukštyn].
- Pakartokite 3, 4 ir 5 žingsnius, kol 5 veiksme nepavyks (ty <<žemas), o tada pakeiskite A [aukštyn] su raktu.
- Jei elementai, esantys kairėje pusėje, yra mažesni už raktą, o raktų dešinėje esantys elementai yra didesni už raktą, masyvas yra padalintas į dvi dalines masyvus.
- Pirmiau minėta procedūra yra pakartotinai taikoma subarijų, kol visa masyvas yra rūšiuojamas.
Privalumai ir trūkumai
Jis turi gerą vidutinį atvejo elgesį. Greitos rūšies veikimo laiko sudėtingumas yra geras, ty jis yra greitesnis nei algoritmai, tokie kaip burbuliukų rūšiavimas, įterpimo rūšiavimas ir parinkimas. Tačiau tai yra sudėtinga ir labai rekursyvi, todėl ji netinka didelėms matricoms.
Sujungimo rūšiavimo apibrėžimas
Sujungti rūšiuoti yra išorinis algoritmas, kuris taip pat grindžiamas pasidalijimo ir užkariavimo strategija. Elementai yra suskirstyti į sub-masyvus (n / 2) dar kartą, kol paliekamas tik vienas elementas, kuris žymiai sumažina rūšiavimo laiką. Jis naudoja papildomą saugyklą pagalbinei matricai saugoti. Sujungimo tvarka naudojama trys matricos, kuriose du yra naudojami kiekvienai pusei saugoti, o trečiasis naudojamas galutiniam surūšiuotam sąrašui išsaugoti. Po to kiekviena masyvas surūšiuoja rekursiškai. Pagaliau, subariarai sujungiami, kad jis taptų masyvo n elemento dydžiu. Šis sąrašas visada suskirstytas į tik pusę (n / 2), skirtingo nuo greito rūšiavimo.
Leiskite A būti n rūšiuojamų elementų masyvas A [1], A [2], ………, A [n]. Sujungimo tvarka atitinka nurodytus veiksmus.
- Masyvą A suskirstykite į maždaug n / 2 rūšiuojamą sub-masyvą 2, o tai reiškia, kad elementai (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]) (A [n-1], A [n]) sub-masyvai turi būti rūšiuojami.
- Sujunkite kiekvieną porų porą, kad gautumėte suskirstytų subarijų sąrašą, kurio dydis yra 4; subarijų elementai taip pat yra rūšiuojami, (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]).
- 2 žingsnis yra pakartotinai atliekamas tol, kol yra tik viena rūšiuojama masyvo dydžio n.
Privalumai ir trūkumai
Sujungimo rūšiavimo algoritmas veikia tiksliai ir tiksliai, neatsižvelgiant į tai, kiek elementų yra susiję su rūšiavimu. Jis veikia net ir su dideliu duomenų rinkiniu. Tačiau ji sunaudoja didesnę atminties dalį.
Pagrindiniai skirtumai tarp greito rūšiavimo ir sujungimo
- Sujungimo tvarka masyvas turi būti padalintas į dvi dalis (ty n / 2). Greitai surūšiuoti nėra jokios prievartos suskirstyti sąrašą į vienodus elementus.
- Blogiausio greito rūšiavimo sudėtingumas yra O (n2), nes blogiausioje situacijoje reikia daug daugiau palyginimų. Priešingai, sujungimo rūšys turi tokį patį blogiausią ir vidutinį atvejų sudėtingumą, ty O (n log n).
- Sujungimo rūšys gali gerai veikti bet kokio tipo duomenų rinkiniuose, nesvarbu, ar ji yra didelė, ar maža. Priešingai, greitas rūšiavimas negali dirbti su dideliais duomenų rinkiniais.
- Kai kuriais atvejais, pvz., Mažų duomenų rinkinių atveju, greitas rūšiavimas yra greitesnis nei sujungimas.
- Suderinti rūšiuoti reikia papildomos atminties vietos, kad būtų galima išsaugoti pagalbines matricas. Kita vertus, greitam rūšiavimui nereikia daug vietos papildomam saugojimui.
- Sujungimas yra efektyvesnis nei greitas.
- Greitas rūšiavimas yra vidinis rūšiavimo metodas, kai duomenys, kurie turi būti surūšiuoti, koreguojami pagrindinėje atmintyje. Ir atvirkščiai, sujungimo tvarka yra išorinis rūšiavimo metodas, kuriame surūšiuoti duomenys negali būti laikomi atmintyje tuo pačiu metu, o kai kurie turi būti laikomi pagalbinėje atmintyje.
Išvada
Greitas sutrumpinimas yra greitesnis atvejis, tačiau kai kuriose situacijose jis neveiksmingas ir atlieka daug palyginimų, palyginti su sujungimu. Nors susiejimas reikalauja mažiau palyginimo, jam reikia papildomos atminties vietos 0 (n), kad būtų galima saugoti papildomą masyvą, o greitai rūšiuoti reikia vietos O (log n).
