Vsebina

• Primerjalna tabela
• Opredelitev hitrega razvrščanja
• Opredelitev Razvrsti spajanje
• Zaključek

Algoritmi za hitro razvrščanje in spajanje temeljijo na algoritmu »deli in osvoji«, ki deluje na povsem podoben način. Predhodna razlika med hitro in združevalno razvrstitvijo je v tem, da se pri razvrščanju uporablja vrtilni element. Po drugi strani sorta spajanja ne uporablja vrtilnega elementa za izvajanje razvrščanja.

Obe tehniki razvrščanja, hitro razvrščanje in združevanje sta zasnovani na metodi razdelitve in osvajanja, pri kateri se nabor elementov razdeli in nato po preurejanju združi. Hitro razvrščanje običajno zahteva več primerjav kot združevanje za razvrščanje velikega nabora elementov.

1. 1. Primerjalna tabela
   2. Opredelitev
   3. Ključne razlike
   4. Zaključek

Primerjalna tabela

Osnove za primerjavo	Hitro razvrščanje	Združite sorto
Razdelitev elementov v matriki	Razdelitev seznama elementov ni nujno razdeljena na polovico.	Niz je vedno razdeljen na polovico (n / 2).
Najslabša zapletenost primera	O (n2)	O (n log n)
Dobro deluje naprej	Manjši niz	Deluje odlično v poljubni vrsti matrike.
Hitrost	Hitrejša od drugih algoritmov za razvrščanje majhnih podatkovnih nizov.	Dosledna hitrost v vseh vrstah podatkovnih nizov.
Dodatna zahteva za shranjevalni prostor	Manj	Več
Učinkovitost	Neučinkovit za večje nize.	Bolj učinkovit.
Način razvrščanja	Notranje	Zunanji

Opredelitev hitrega razvrščanja

Hitro razvrščanje je razširjen algoritem razvrščanja, saj je hiter za kratke matrike. Nabor elementov je večkrat razdeljen na dele, dokler ga ni mogoče razdeliti naprej. Hitro razvrščanje je znano tudi kot vrsta izmenjave particij. Za razdelitev elementov uporablja ključni element (znan kot vrtilni element). 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 niz A, A, A, …… .., A n števila, ki jih je treba razvrstiti. Algoritem za hitro razvrščanje je vseboval naslednje korake.

1. Prvi element ali kateri koli naključni element, izbran kot ključ, predpostavimo, da je ključ = A (1).
2. Kazalnik „nizko“ je postavljen na drugi in kazalec „gor“ je nameščen na zadnjem elementu matrike, to je nizko = 2 in navzgor = n;
3. Določite, da „nizki“ kazalec povečujete za en položaj do (A> tipka).
4. Nenehno kazalec navzgor usmerjajte za en položaj, dokler ne pritisnete (A <= tipka).
5. Če je gor večji od nizkega, izmenjava A z A.
6. Ponavljajte korak 3,4 in 5, dokler stanje v koraku 5 ne uspe (tj. Navzgor <= nizko), nato zamenjajte A s tipko.
7. Če so elementi, ki so levi od ključa, manjši od ključa in so elementi desne od ključa večji od ključa, potem je matrika razdeljena na dva podračuna.
8. Zgornji postopek se večkrat uporabi za podravlične nivoje, dokler ni urejen celoten niz.

   

   
   

Prednosti in slabosti

Ima dobro povprečno vedenje primera. Hitrost zahtevnosti hitrega razvrščanja je dobra, saj je hitrejša od algoritmov, kot so razvrščanje mehurčkov, sortiranje vstavitve in izbira. Vendar je zapleten in zelo rekurziven, zato ni primeren za velike matrike.

Opredelitev Razvrsti spajanje

Združite sorto je zunanji algoritem, ki temelji tudi na strategiji delitve in osvajanja. Elemente znova in znova razdelimo na podračunove (n / 2), dokler ne ostane samo en element, kar bistveno zmanjša čas razvrščanja. Za shranjevanje pomožnega niza uporablja dodatni pomnilnik. Razvrsti sorta uporablja tri matrike, kjer se dva uporabljajo za shranjevanje vsake polovice, tretji pa se uporablja za shranjevanje končnega razvrščenega seznama. Vsak sklop je nato urejen rekurzivno. Končno se podenote združijo, tako da je n element velikosti matrike. Seznam je vedno razdeljen na samo polovico (n / 2), ki se razlikuje od hitrega razvrščanja.

Naj bo A niz niza elementov, ki jih je treba razvrstiti A, A, ………, A. Razvrstitev po združevanju sledi danim korakom.

1. Niz A razdelite na približno n / 2 razvrstitev podzvrsti po 2, kar pomeni, da se morajo elementi v (A, A), (A, A), (A, A), (A, A) podreseju biti v urejenem vrstnem redu.
2. Združite vsak par parov, da dobite seznam razvrščenih podravlič velikosti 4; elementi v poddrugih so tudi v razvrščenem vrstnem redu, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Korak 2 se večkrat izvede, dokler ni le enega razvrščenega niza velikosti n.

   

Prednosti in slabosti

Algoritem razvrščanja združevanja deluje popolnoma enako in natančno, ne glede na število elementov, ki so vključeni v razvrščanje. Deluje odlično tudi z velikim naborom podatkov. Vendar porabi večji del spomina.

1. Pri razvrstitvi združitve mora biti matrika razdeljena na samo dve polovici (tj. N / 2). V nasprotju s hitro razvrstitvijo seznama ni na silo razdeliti na enake elemente.
2. Najhujša zapletenost hitrega razvrščanja je O (n²), saj je v najslabšem stanju potrebnih veliko več primerjav. V nasprotju s tem imajo vrste združevanja enake najslabše in povprečne zapletenosti primerov, to je O (n log n).
3. Razvrstitev združevanja lahko dobro deluje na kateri koli vrsti podatkovnih zbirk, ne glede na to, ali je velika ali majhna. Nasprotno, hitro razvrščanje ne more dobro delovati z velikimi nabori podatkov.
4. Hitro razvrščanje je hitrejše od združevanja v nekaterih primerih, na primer za majhne podatkovne naloge.
5. Razvrstitev združitve zahteva dodaten pomnilniški prostor za shranjevanje pomožnih nizov. Po drugi strani pa za hitro sortiranje ni potrebno veliko prostora za dodatno shranjevanje.
6. Razvrsti spajanje je učinkovitejše od hitrega razvrščanja.
7. Hitro razvrščanje je notranja metoda razvrščanja, pri kateri se podatki, ki jih je treba razvrstiti, prilagodijo v glavnem pomnilniku. Nasprotno je sortiranje združevanja zunanja metoda razvrščanja, pri kateri podatkov, ki jih je treba razvrstiti, ni mogoče istočasno namestiti v pomnilnik, nekatere pa hraniti v pomožnem pomnilniku.

Zaključek

Hitra razvrstitev je hitrejša, vendar je v nekaterih situacijah neučinkovita in tudi v primerjavi z razvrstitvijo združi veliko primerjav. Čeprav je za združevanje potrebno manj primerjave, potrebuje dodatni pomnilniški prostor 0 (n) za shranjevanje dodatnega niza, medtem ko hitro razvrščanje potrebuje prostor O (log n).