Sadržaj

• Usporedni grafikon
• Definicija brzog razvrstavanja
• Definicija sortiranja spajanja
• Zaključak

Algoritmi za brzo sortiranje i spajanje temelje se na algoritmu podijeli i osvoji, koji djeluje na sasvim sličan način. Prethodna razlika između brzine i spajanja sorte je da se u brzom razvrstavanju stožerni element koristi za razvrstavanje. S druge strane, vrsta spajanja ne koristi element stožišta za obavljanje sortiranja.

Obje tehnike sortiranja, brzo sortiranje i spajanje sortiraju se na osnovi dijeljenja i osvajanja u kojem se skup elemenata dijeli, a zatim kombinira nakon preuređenja. Brzo razvrstavanje obično zahtijeva više usporedbi nego spajanje za sortiranje velikog skupa elemenata.

1. 1. Usporedni grafikon
   2. definicija
   3. Ključne razlike
   4. Zaključak

Usporedni grafikon

Osnove za usporedbu	Brza vrsta	Spajanje vrsta
Podjela elemenata u nizu	Podjela popisa elemenata nije nužno podijeljena na pola.	Niz je uvijek podijeljen na pola (n / 2).
Najgora složenost slučaja	Na2)	O (n zapis n)
Dobro uspijeva	Manji niz	Dobro funkcionira u bilo kojoj vrsti polja.
Ubrzati	Brži od ostalih algoritama sortiranja za male skupove podataka.	Ujednačena brzina u svim vrstama podataka.
Dodatni uvjeti prostora za pohranu	Manje	Više
efikasnost	Neučinkovit za veće nizove.	Učinkovitije.
Način sortiranja	interni	Vanjski

Definicija brzog razvrstavanja

Brza vrsta je rašireni algoritam sortiranja jer je brz za kratke nizove. Skup elemenata podijeljen je u dijelove više puta dok ih nije moguće dalje podijeliti. Brza sorta je također poznata kao vrsta razmjene particija, Za particioniranje elemenata koristi ključni element (poznat kao zgib). Jedna particija sadrži one elemente koji su manji od ključnog elementa. Druga particija sadrži one elemente koji su veći od ključnog elementa. Elementi su razvrstani rekurzivno.

Pretpostavimo da je A niz A, A, A, …… .., A od n broja koji je potrebno sortirati. Algoritam za brzo razvrstavanje sastojao se od sljedećih koraka.

1. Prvi element ili bilo koji slučajni element odabran kao ključ, pretpostavimo da je ključ = A (1).
2. Pokazivač "nizak" nalazi se na drugom, a pokazivač "gore" postavljen je na posljednji element polja, tj. Nizak = 2 i gore = n;
3. Dosljedno, povećavajte pokazivač "nisko" za jedno mjesto do (A> tipka).
4. Stalno, usmjerivati ​​pokazivač "gore" za jedan položaj do (A <= tipka).
5. Ako je gore veći od niskog, izmjenjujte A s A.
6. Ponavljajte korak 3,4 i 5 sve dok uvjet iz koraka 5 ne uspije (tj. Gore <= nizak), a zatim razmijenite A s tipkom.
7. Ako su elementi lijevi od ključa manji od ključa, a elementi desno od ključa, veći su od ključa, tada je niz podijeljen na dva podreda.
8. Gornji postupak se opetovano primjenjuje na podraslima sve dok se cijeli niz ne razvrsta.

   

   
   

Prednosti i nedostatci

Ima dobro prosječno ponašanje slučaja. Složenost brzine rada brzog sortiranja je dobra što je brža od algoritama poput sortiranja mjehurića, sortiranja umetanja i odabira. Međutim, to je složeno i vrlo rekurzivno, to je razlog što nije prikladan za velike nizove.

Definicija sortiranja spajanja

Spajanje vrsta je vanjski algoritam koji se također temelji na strategiji dijeljenja i osvajanja. Elementi se dijele na podskupine (n / 2) iznova i iznova dok ne ostane samo jedan element, što značajno smanjuje vrijeme sortiranja. Koristi dodatni prostor za pohranu pomoćnog niza. Razvrstavanje sortiranja koristi tri polja u kojima se dva koriste za pohranjivanje svake polovine, a treća se koristi za spremanje konačnog poredanog popisa. Zatim se svaki niz sortira rekurzivno. Konačno, podrasla su spojena tako da čine n element veličine polja. Popis je uvijek podijeljen na samo pola (n / 2) različita od brzog sortiranja.

Neka je A niz niza elemenata koji će se sortirati A, A, ………, A. Sorta sortiranja slijedi dane korake.

1. Podijelite niz A na približno n / 2 razvrstani pod-niz na 2, što znači da se elementi u (A, A), (A, A), (A, A), (A, A) pod-nizu moraju biti u razvrstanom redoslijedu.
2. Kombinirajte svaki par parova kako biste dobili popis razvrstanih podvrsta veličine 4; elementi u podraslima su također poredani redoslijedom, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Korak 2 se opetovano izvodi sve dok ne postoji samo jedan sortirani niz veličine n.

   

Prednosti i nedostatci

Algoritam sortiranja spajanja izvodi se na potpuno isti i precizan način bez obzira na broj elemenata koji su uključeni u razvrstavanje. Odlično funkcionira čak i s velikim skupom podataka. Međutim, troši veći dio memorije.

1. U vrsti spajanja, niz se mora rastaviti na samo dvije polovice (tj. N / 2). Za razliku od toga, u brzom sortiranju ne postoji prisiljavanje dijeljenja popisa na jednake elemente.
2. Najgora složenost brzog sortiranja je O (n²) jer je u najgorem stanju potrebno puno više usporedbi. Suprotno tome, vrste spajanja imaju jednake najgore slučajeve i prosječne složenosti slučaja, to jest O (n log n).
3. Razvrstavanje vrsta spajanja može dobro funkcionirati na bilo kojoj vrsti podataka, bilo da je velika ili mala. Suprotno tome, brza vrsta ne može dobro funkcionirati s velikim skupovima podataka.
4. Brzo sortiranje je brže od spajanja sortiranja u nekim slučajevima, primjerice za male skupove podataka.
5. Spajanje vrste zahtijeva dodatni memorijski prostor za spremanje pomoćnih nizova. S druge strane, brzo sortiranje ne zahtijeva mnogo prostora za dodatnu pohranu.
6. Razvrstavanje spajanja je učinkovitije od brzog sortiranja.
7. Brza vrsta je interna metoda sortiranja, gdje se podaci koji se trebaju sortirati podešavaju istodobno u glavnoj memoriji. Suprotno tome, vrsta spajanja je metoda vanjskog sortiranja u kojoj se podaci koji se trebaju sortirati ne mogu istovremeno smjestiti u memoriju, a neki moraju čuvati u pomoćnoj memoriji.

Zaključak

Brzo razvrstavanje je brži, ali u nekim je situacijama neučinkovito i u usporedbi s vrstama spajanja obavlja mnogo usporedbi. Iako je za razvrstavanje potrebno manje usporedbe, potreban je dodatni memorijski prostor od 0 (n) za pohranjivanje dodatnog niza, dok brzom razvrstavanju treba prostor O (log n).