Razlika med sortiranjem po hitrem razvrščanju in spajanju

• 2019

Hitri razvrščanje in združevanje algoritmov temeljijo na algoritmu deljenja in vladanja, ki deluje na precej podoben način. Predhodna razlika med hitrim in spajalnim razvrščanjem je, da se v sortiranju hitro uporablja sortirni element. Po drugi strani pa sortiranje spajanja ne uporablja pivot elementa za opravljanje razvrščanja.

Obe metodi razvrščanja, hitro sortiranje in spajanje so zgrajeni na metodi razdelitve in vladanja, pri kateri se niz elementov razdeli in nato združi po prerazporeditvi. Hitra vrsta ponavadi zahteva več primerjav kot sortiranje za razvrščanje velikega števila elementov.

Primerjalna tabela

Podlaga za primerjavo	Hitro razvrščanje	Spoji razvrstitev
Razdelitev elementov v matriki	Razdelitev seznama elementov ni nujno razdeljena na polovico.	Array je vedno razdeljen na polovico (n / 2).
Najslabša zadeva	O (n2)	O (n log n)
Dobro deluje	Manjše polje	Deluje dobro v poljubni vrsti matrike.
Hitrost	Hitrejši od drugih sortirnih algoritmov za nizke podatkovne nize.	Dosledna hitrost v vseh vrstah podatkovnih nizov.
Potreba po dodatnem prostoru za shranjevanje	Manj	Več
Učinkovitost	Neučinkovito pri večjih nizih.	Bolj učinkovit.
Metoda razvrščanja	Notranji	Zunanji

Opredelitev hitrega razvrščanja

Hitro razvrščanje je vsekakor uporabljen algoritem za razvrščanje, saj je hiter za kratka polja. Komplet elementov je večkrat razdeljen na dele, dokler ni mogoče nadalje razdeliti. Hitro razvrščanje je znano tudi kot razvrščanje prekatov . Za razdelitev elementov uporablja ključni element (znan kot pivot). Ena particija vsebuje tiste elemente, ki so manjši od ključnega elementa. Druga particija vsebuje tiste elemente, ki so večji od ključnega elementa. Elementi so razvrščeni rekurzivno.

Recimo, da je A matrika A [1], A [2], A [3], ……, A [n] števila n, ki jih je treba razvrstiti. Hitri algoritem razvrščanja vsebuje naslednje korake.

1. Prvi element ali kateri koli naključni element, izbran kot ključ, predvideva ključ = A (1).
2. Kazalec »nizka« je postavljen na drugi in »navzgor« kazalec je postavljen na zadnji element matrike, tj. Nizko = 2 in navzgor = n;
3. Dosledno povečajte kazalec »nizko« za en položaj, dokler (tipka [A]).
4. Nenehno zmanjšujte kazalec navzgor za en položaj, dokler (A [gor] <= tipka).
5. Če je navzgor večja od nizke izmenjave A [nizko] z A [gor].
6. Ponovite korake 3, 4 in 5, dokler pogoj v koraku 5 ne uspe (tj. Navzgor <= nizko), nato pa izmenjujete A [gor] s tipko.
7. Če so elementi levo od ključa manjši od ključa in so elementi desno od ključa večji od ključa, je polje razčlenjeno na dve podarjavi.
8. Zgornji postopek se večkrat uporablja za podarže, dokler ni celotno polje razvrščeno.

Prednosti in slabosti

Ima dobro povprečno obnašanje primerov. Časovna zahtevnost hitrega razvrščanja je dobra, da je hitrejša od algoritmov, kot so razvrščanje mehurčkov, sortiranje vstavljanja in sortiranje. Vendar pa je kompleksen in zelo rekurziven, zato ni primeren za velike matrike.

Opredelitev vrste združevanja

Sortiranje spajanja je zunanji algoritem, ki prav tako temelji na strategiji deljenja in vladanja. Elementi se znova in znova delijo v podarje (n / 2), dokler ni le en element, kar bistveno zmanjša čas razvrščanja. Uporablja dodatni pomnilnik za shranjevanje pomožnega polja. Merge sort uporablja tri matrike, kjer sta dva uporabljena za shranjevanje vsake polovice, tretji pa se uporablja za shranjevanje končnega sortiranega seznama. Vsako polje se nato razvrsti rekurzivno. Nazadnje se subarrays združijo, tako da postane n velikost elementa matrike. Seznam je vedno razdeljen na samo polovico (n / 2), ki je različna od hitre vrste.

Naj bo A matrika iz n števila elementov, ki jih je treba razvrstiti A [1], A [2], ………, A [n]. Vrsta združevanja sledi danim korakom.

1. Razdeli matriko A v približno n / 2 razvrščeno sub-polje z 2, kar pomeni, da so elementi v (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) podparametri morajo biti v urejenem vrstnem redu.
2. Združite vsak par parov, da dobite seznam razvrščenih podarin velikosti 4; elementi v podpodročjih so tudi razvrščeni, (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. Korak 2 se večkrat izvaja, dokler ni samo ena razvrščena matrika velikosti n.

Prednosti in slabosti

Algoritem za razvrščanje spajkanja se izvede na enak in natančen način, ne glede na število elementov, vključenih v razvrščanje. Deluje v redu tudi z veliko podatkovno zbirko. Vendar pa porabi večji del pomnilnika.

Ključne razlike med sortiranjem po hitrem razvrščanju in spajanju

1. V razvrstitvi spajanja mora biti matrika razdeljena na samo dve polovici (tj. N / 2). V nasprotju s tem, da se hitro razvrsti, ni prisile delitve seznama na enake elemente.
2. Najslabši primer je hitra razvrstitev O (n2), saj je v najslabšem stanju potrebno veliko več primerjav. Nasprotno imajo sorte spajanja enako najslabšo možnost in povprečne zapletenosti primera, to je O (n log n).
3. Razvrstitev spajanja lahko deluje dobro na vseh vrstah podatkovnih nizov, ne glede na to, ali je velika ali majhna. Ravno nasprotno, hitra vrsta ne more dobro delovati z velikimi podatkovnimi nizi.
4. Hitro razvrščanje je v nekaterih primerih hitrejše kot razvrščanje v združevanje, na primer za majhne podatkovne nize.
5. Vrsta spajanja potrebuje dodaten pomnilniški prostor za shranjevanje pomožnih polj. Po drugi strani hitra vrsta ne zahteva veliko prostora za dodatno shranjevanje.
6. Vrsta združevanja je bolj učinkovita kot hitra vrsta.
7. Hitra vrsta je metoda internega razvrščanja, kjer se podatki, ki jih želite razvrstiti, prilagajajo hkrati v glavnem pomnilniku. Nasprotno pa je vrsta spajanja zunanji način razvrščanja, pri katerem podatkov, ki jih je treba razvrstiti, ni mogoče hkrati shraniti v pomnilnik, nekatere pa je treba hraniti v pomožnem pomnilniku.

Zaključek

Hitro razvrščanje je hitrejše, vendar je v nekaterih situacijah neučinkovito in opravlja veliko primerjav v primerjavi s spajanjem. Čeprav razvrščanje spajanja zahteva manj primerjave, potrebuje dodatni pomnilniški prostor 0 (n) za shranjevanje dodatnega niza, medtem ko hitro sortiranje potrebuje prostor O (log n).