Turinys

• Palyginimo diagrama
• Greito rūšiavimo apibrėžimas
• Apjungimo rūšiavimo apibrėžimas
• Išvada

Greito rūšiavimo ir sujungimo algoritmai yra pagrįsti dalijimo ir užkariavimo algoritmu, kuris veikia gana panašiai. Ankstesnis skirtumas tarp greitojo ir sujungiamojo rūšiavimo yra tas, kad greitajame rūšiavime naudojamas šarnyrinis elementas. Kita vertus, suliejant rūšiavimą nenaudojamas šarnyrinis elementas.

Tiek rūšiavimo būdai, tiek greitasis rūšiavimas, tiek sujungimo rūšiavimas yra paremti dalijimosi ir užkariavimo metodu, kai elementų rinkinys yra padalijamas ir sujungiamas po pertvarkymo. Greitam rūšiavimui paprastai reikia daugiau palyginimų nei norint sujungti, norint surūšiuoti didelį elementų rinkinį.

1. 1. Palyginimo diagrama
   2. Apibrėžimas
   3. Pagrindiniai skirtumai
   4. Išvada

Palyginimo diagrama

Palyginimo pagrindas	Greitas rūšiavimas	Sujungti rūšiuoti
Elementų padalijimas į masyvą	Elementų sąrašo padalijimas nebūtinai padalijamas į pusę.	Masyvas visada padalijamas į pusę (n / 2).
Blogiausias atvejo sudėtingumas	O (n2)	O (n log n)
Gerai veikia	Mažesnis masyvas	Tinka bet kokio tipo matricoms.
Greitis	Greičiau nei kiti mažo duomenų rinkinio rūšiavimo algoritmai.	Nuoseklus greitis visų tipų duomenų rinkiniuose.
Papildomos vietos saugyklai reikalavimas	Mažiau	Daugiau
Efektyvumas	Neefektyvus didesnėms matricoms.	Efektyvesnis.
Rūšiavimo būdas	Vidinis	Išorinis

Greito rūšiavimo apibrėžimas

Greitas rūšiavimas yra plačiai naudojamas rūšiavimo algoritmas, nes jis yra greitas trumpiems masyvams. Elementų rinkinys pakartotinai padalijamas į dalis, kol jo neįmanoma padalinti toliau. Greitasis rūšiavimas taip pat žinomas kaip pertvarų mainų rūšiavimas. Elementams skaidyti naudojamas pagrindinis elementas (žinomas kaip šarnyras). Viename skaidinyje yra tie elementai, kurie yra mažesni už pagrindinį elementą. Kitame skaidinyje yra tie elementai, kurie yra didesni už pagrindinį elementą. Elementai rūšiuojami rekursyviai.

Tarkime, A yra masyvas A, A, A, …… .., A iš n skaičiaus, kurie turi būti rūšiuojami. Greito rūšiavimo algoritmas susideda iš šių žingsnių.

1. Pirmasis elementas arba bet koks atsitiktinis elementas, pasirinktas kaip raktas, prisiima raktą = A (1).
2. „Žemas“ rodyklė dedama į antrą, o „aukštyn“ rodyklė - į paskutinį masyvo elementą, ty žemas = 2 ir aukščiau = n;
3. Nuosekliai padidinkite „žemą“ rodyklę viena padėtimi, kol (A> mygtukas).
4. Nuolat mažinkite rodyklę „aukštyn“ viena padėtimi, kol (A <= raktas).
5. Jei aukštyn yra daugiau nei žemas apsikeitimas A su A.
6. Pakartokite 3,4 ir 5 veiksmus, kol 5 žingsnio sąlygos nepavyks (t. Y. Aukščiau <= žemas), tada keiskite A klavišu.
7. Jei rakto kairieji elementai yra mažesni už raktą, o rakto dešinieji elementai yra didesni už raktą, tada masyvas yra padalijamas į dvi dalis.
8. Aukščiau aprašyta procedūra pakartotinai taikoma subarizmams, kol bus surūšiuotas visas masyvas.

   

   
   

Privalumai ir trūkumai

Paprastai jis elgiasi gerai. Greitas rūšiavimo laikas yra sudėtingas, ty jis yra greitesnis nei algoritmai, tokie kaip burbulų rūšiavimas, intarpų rūšiavimas ir pasirinkimo rūšiavimas. Tačiau jis yra sudėtingas ir labai pasikartojantis, todėl jis netinka dideliems masyvams.

Apjungimo rūšiavimo apibrėžimas

Sujungti rūšiuoti yra išorinis algoritmas, kuris taip pat pagrįstas dalijimo ir užkariavimo strategija. Elementai vėl ir vėl padalijami į dalinius masyvus (n / 2), kol liko tik vienas elementas, o tai žymiai sumažina rūšiavimo laiką. Pagalbiniam masyvui laikyti naudojama papildoma saugykla. Sujungimo rūšiavimui naudojami trys masyvai, kur kiekvienai pusei saugoti naudojami du, o trečiasis naudojamas galutiniam išrūšiuotam sąrašui saugoti. Tada kiekvienas masyvas rūšiuojamas rekursyviai. Pagaliau subpakečiai sujungiami, kad masyvo elemento dydis būtų n. Sąrašas visada buvo padalintas į pusę (n / 2), nesiskiriančių nuo greito rūšiavimo.

Tegul A yra n skaičių elementų, kurie turi būti rūšiuojami, masyvas A, A, ………, A. Sujungimo rūšis seka nurodytais žingsniais.

1. Padalinkite masyvą A į apytiksliai n / 2 surūšiuotą antrąjį masyvą iš 2, tai reiškia, kad elementai, esantys (A, A), (A, A), (A, A), (A, A) pogrupiuose, turi būti būti surūšiuota tvarka.
2. Sujunkite kiekvieną porą, kad gautumėte 4 dydžio išrūšiuotų porūšių sąrašą; elementai, esantys apatiniuose sluoksniuose, taip pat yra surūšiuoti (A, A, A, A), …… (A, A, A, A), ……. (A, A, A, A).
3. 2 veiksmas pakartojamas pakartotinai, kol nėra tik vieno n rūšies surūšiuoto masyvo.

   

Privalumai ir trūkumai

Sujungimo rūšiavimo algoritmas vykdomas tiksliai ir tiksliai, neatsižvelgiant į rūšiavime dalyvaujančių elementų skaičių. Jis puikiai veikia net esant dideliam duomenų rinkiniui. Tačiau jis sunaudoja didesnę atminties dalį.

1. Sujungiant rūšiuoti, masyvas turi būti padalintas į dvi dalis (t. Y. N / 2). Greita rūšiavimo tvarka nėra prievarta dalijant sąrašą į lygius elementus.
2. Blogiausias greito rūšiavimo sudėtingumas yra O (n²), nes blogiausioje būklėje reikia daug daugiau palyginimų. Priešingai, sujungimo rūšys turi tą patį blogiausią atvejį ir vidutinį atvejo sudėtingumą, tai yra O (n log n).
3. Sujungti rūšiavimas gali gerai veikti su bet kokio tipo duomenų rinkiniais, nesvarbu, ar jie yra dideli, ar maži. Greitasis rūšiavimas, priešingai, negali efektyviai veikti esant didelėms duomenų rinkinėms.
4. Kai kuriais atvejais greitas rūšiavimas yra greitesnis nei sujungimas, pavyzdžiui, mažų duomenų rinkinių atveju.
5. Norint sujungti rūšiavimą, reikia papildomos atminties, kad būtų galima laikyti pagalbinius masyvus. Kita vertus, greitam rūšiavimui nereikia daug vietos papildomai saugyklai.
6. Rūšiuoti sujungus yra efektyviau nei greitai.
7. Greitasis rūšiavimas yra vidinio rūšiavimo metodas, kai duomenys, kurie turi būti rūšiuojami, vienu metu koreguojami pagrindinėje atmintyje. Atvirkščiai, sujungimo rūšiavimas yra išorinis rūšiavimo būdas, kai duomenys, kurie turi būti rūšiuojami, negali būti talpinami atmintyje tuo pačiu metu, o kai kurie turi būti laikomi papildomoje atmintyje.

Išvada

Greitasis rūšiavimas yra greitesnis, bet kai kuriose situacijose neveiksmingas, be to, jis daug lyginamas, palyginti su sujungimo rūšiavimu. Nors norint sujungti rūšiavimą reikia mažiau palyginti, reikia papildomos 0 (n) atminties vietos, kad būtų galima saugoti papildomą masyvą, o greitam rūšiavimui reikia O vietos (log n).