Obje tehnike razvrstavanja, sortiranje brzih sorti i spajanja izgrađene su na metodi podjele i osvajanja u kojoj se skup elemenata razdijeli i zatim kombinira nakon pregrađivanja. Brza vrsta obično zahtijeva više usporedbi od sortiranja za spajanje velikog skupa elemenata.
Tablica usporedbe
| Osnova za usporedbu | Brzo sortiranje | Spoji sort |
|---|---|---|
| Particioniranje elemenata u nizu | Podjela popisa elemenata nije nužno podijeljena na pola. | Array se uvijek dijeli na pola (n / 2). |
| Najgori slučaj složenosti | O (n2) | O (n log n) |
| Dobro radi | Manji niz | Dobro funkcionira u bilo kojoj vrsti polja. |
| Ubrzati | Brži od ostalih algoritama sortiranja za male skupove podataka. | Dosljedna brzina u svim vrstama skupova podataka. |
| Potreban dodatni prostor za pohranu | Manje | Više |
| efikasnost | Neučinkovito za veće nizove. | Učinkovitije. |
| Metoda sortiranja | interni | Vanjski |
Definicija brzog sortiranja
Brzo sortiranje je rašireno korišten algoritam sortiranja jer je brz za kratke nizove. Skup elemenata je više puta podijeljen na dijelove dok ga nije moguće dalje podijeliti. Brzo sortiranje je također poznato kao vrsta razmjene particija . Ona koristi ključni element (poznat kao pivot) za particioniranje elemenata. 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 [1], A [2], A [3], ……, A [n] od n broja koji treba sortirati. Brzi algoritam sortiranja sastoji se od sljedećih koraka.
- Prvi element ili bilo koji slučajni element odabran kao ključ pretpostavlja ključ = A (1).
- "Low" pokazivač se nalazi na drugom, a "up" pokazivač je pozicioniran na posljednjem elementu polja, tj. Low = 2 i up = n;
- Dosljedno povećavajte pokazivač "low" za jedan položaj sve dok (A [niska]> tipka).
- Stalno, smanjite pokazivač "gore" za jedan položaj sve dok (A [gore] <= ključ).
- Ako je viši nego niska izmjena A [nisko] s A [gore].
- Ponovite korake 3, 4 i 5 dok se stanje u koraku 5 ne pokvari (tj. Do <= nisko), a zatim izmijenite A [gore] s tipkom.
- Ako su elementi lijevo od ključa manji od ključa, a elementi desno od ključa su veći od ključa, onda je niz particioniran u dva pod-polja.
- Gornji postupak se višekratno primjenjuje na podrabe sve dok se ne sortira cijeli niz.
Prednosti i nedostatci
Posjeduje dobro prosječno ponašanje. Vrijeme rada složenosti brzog sortiranja je dobro što je brže od algoritama kao što su sortiranje mjehurića, sortiranje umetanjem i sortiranje. Međutim, on je složen i vrlo rekurzivan, zbog čega nije prikladan za velike nizove.
Definicija sortiranja spajanja
Spajanje je vanjski algoritam koji se također temelji na strategiji podijeli i osvoji. Elementi se dijele na podarvale (n / 2) iznova i iznova sve dok ne ostane samo jedan element koji značajno smanjuje vrijeme sortiranja. Koristi dodatnu pohranu za spremanje pomoćnog niza. U načinu spajanja koriste se tri polja gdje se dva koriste za pohranu svake polovice, a treći se koristi za spremanje konačne sortirane liste. Svaki niz se zatim sortira rekurzivno. Napokon, subarrays se spajaju tako da je n veličina elementa polja. Popis se uvijek dijeli na samo polovicu (n / 2) različitog od brzog sortiranja.
Neka je A niz od n broja elemenata koje treba razvrstati A [1], A [2], ………, A [n]. Vrsta spajanja slijedi zadane korake.
- Razdvojite polje A u približno n / 2 razvrstanih pod-polja za 2, što znači da elementi u (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], pod-nizovi A [n]) moraju biti sortirani.
- Kombinirajte svaki par parova kako biste dobili popis sortiranih podarara veličine 4; elementi u subarrays su također u sortiranom redoslijedu, (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]).
- Korak 2 se ponavlja sve dok ne postoji samo jedan razvrstani niz veličine n.
Prednosti i nedostatci
Algoritam za sortiranje spajanja izvodi se na isti i precizan način bez obzira na broj elemenata uključenih u sortiranje. To radi u redu čak i s velikim skupom podataka. Međutim, ona troši veći dio memorije.
Ključne razlike između sortiranja brzog sortiranja i spajanja
- U sortiranju spajanja, polje mora biti razdijeljeno na samo dvije polovice (tj. N / 2). Nasuprot tome, u brzom obliku nema prisile dijeljenja popisa na jednake elemente.
- Najgori slučaj složenosti brzog sortiranja je O (n2) jer je potrebno mnogo više usporedbi u najgorem stanju. Nasuprot tome, sorta spajanja ima istu najgorem slučaju i prosječnu složenost slučaja, to jest O (n log n).
- Sortiranje spajanja može dobro funkcionirati na bilo kojoj vrsti skupova podataka bilo da je velika ili mala. Naprotiv, brza vrsta ne može dobro raditi s velikim skupovima podataka.
- Brzo sortiranje je brže od sortiranja spajanja u nekim slučajevima, primjerice kod malih skupova podataka.
- Vrsta spajanja zahtijeva dodatni memorijski prostor za spremanje pomoćnih polja. S druge strane, brza sorta ne zahtijeva puno prostora za dodatno pohranjivanje.
- Vrsta spajanja je učinkovitija od brze vrste.
- Brzo sortiranje je interni način razvrstavanja u kojem se podaci koji se trebaju razvrstati istovremeno podešavaju u glavnoj memoriji. Nasuprot tome, vrsta spajanja je vanjska metoda sortiranja u kojoj se podaci koji se trebaju sortirati ne mogu istovremeno smjestiti u memoriju, a neki se moraju čuvati u pomoćnoj memoriji.
Zaključak
Brzo sortiranje je brži slučaj, ali je u nekim situacijama neučinkovito i također obavlja mnogo usporedbi u odnosu na sortiranje spajanja. Iako sortiranje spajanja zahtijeva manje usporedbe, potrebno mu je dodatno memorijsko mjesto od 0 (n) za pohranjivanje dodatnog niza, dok brzo sortiranje zahtijeva prostor od O (log n).
