Choose jour language!

---

|

SORTIRANJE NIZOVA OBJEDINJAVANJEM
(MERGE - SORT ENGL.)

​Merge Sort ili sortiranje objedinjavanjem je algoritam koji je efikasniji od sortiranja umetanjem, ali nije brži od brzog sortiranja Quick Sort engl. Ideja je da se početni niz rekurzivno razdvaja na dva približno jednaka podniza, levi i desni. Zatim se postupak ponavlja sve dok se ne dođe do dva elementarna niza od 1 ili dva elementa. Zatim krene objadinjavanje ovih elementarnih nizova u složenije i pri tome se oni formiraju da budu sortirani, dakle porede se jedan član levog i jedan član desnog podniza i od njih se sastavlja veći podniz koji sadrži članove oba ova mala niza, ali u ispravnom redosledu, tj. sortirane ili u rastućem ili u opadajućem poretku. Npr.
Pretpostavimo da imamo sledeći niz koji je potrebno sortirati u rastućem redosledu:

Slika 1: Polazni niz

VIDEO: Sortiranje objedinjavanjem

---

 Zadatak može da se reši rekurzijom.
Postupak rekurzivnog poziva funkcije koja vrši sortiranje počinje posle učitavanja ili zadavanja niza. Funkciju možemo nazvati npr razdvajanjeNiza i kao parametre joj proslediti sam niz, početnu poziciju, krajnju poziciju i broj elemenata. Prototip te funkcije bi mogao biti:

void razdvajanjeNiza(int a[], int l,int d,int n);

Funkcija treba da radi sledeće:

• Nađe poziciju približno(0, m) i desni deo(m+1, n) i pokreće dalje deljenje ova dva niza , tako što ponovo poziva samu sebe i prosleđuje kao parametre originalni niz i početnu i krajnu poziciju oba niza.
• Vrši objedinjavanje elementarnih nizova dobijeni prethodnim rekurzijama.

Na sledećoj slici mogu se videti početne i krajnje pozicije, levog i desnog niza:

Deljenje niza na manje podnizove

Slika 2: Sortiranje objedinjavanjem. Razdvajanje na manje nizove

​U sledećoj iteraciji podeliće se početni niz na dva niza kada se ta iteracija kompletno završi, a to će se ostvariti tek kad se završe sve naknadno pozvane iteracije. Deoba niza bi izgledala kao na sledećoj slici:

Slika 3: Sortiranje objedinjavanjem. Deljenje na manje podnizove

​Metoda koja to radi bi bila:

void razdvajanjeNiza(int a[], int l,int d,int n)
{

int m=(l+d)/2;
if(l < d)
{

razdvajanjeNiza(a, l, m, n); //Levu polovina posmatranog podniza
razdvajanjeNiza(a, m+1, d, n); //desna polovina posmatranog podniza
spajanjeNizova(a, l, m, d, n); //spajanje legog i desnog. U povratku sa rekurzije spajaju se vec sortirane polovine

}
return;

}

​Rekurzivni postupak razdvajanja bi se slikovito mogao prikazati:

Slika 3: Sortiranje objedinjavanjem. Deljenje na manje podnizove. Četvrta i peta iteracija

​Funkcija koja vrši razdvajanje:

Slika 4: Sortiranje objedinjavanjem. Deljenje na manje podnizove - funkcija

---

Slika 5: Sortiranje objedinjavanjem. Deljenje na manje podnizove - funkcija, tok izvršenja

---

Kada se završi razdvajanje niza na elementarne vrši se spajanje elementarnih nizova u veće nizove i pri tome se vrši sortiranje istih:

Slika 6: Sortiranje objedinjavanjem. Spajanje manjih u veće nizove-shema

Posmatrajmo postupak spajanja u 3. iteracije koja je prikazana zelenom bojom na prethodnoj slici. Iteracije se  sada broje odozdo naviše. Posmatrajmo dva niza: {3, 5, 10} i {-34, 16}.
Posle spajanja dobiće se: {-34, 3, 5, 10, 16}
Funkcija koja to radi:

void spajanjeNizova(int a[ ], int l, int m, int d, int n)
{

int k, i, j;
int aCopy[n];
for(int i=0; i < n; i++)
{

aCopy[i]=a[i];

}

}

Originalni niz a je prosleđen kao parametar, kao i odgovarajuće pozicije: leva l, desna d i srednja m, kao i dimenzija niza n.
Kroz petlju upoređujemo vrednost
 na tekućoj poziciji levog niza unutar kopije
sa
 vrednosti na tekućoj poziciji desnog dela kopije niza:

void spajanjeNizova(int a[ ], int l, int m, int d, int n)
{

int k, i, j;
int aCopy[ n ];
for(int i=0; i < n; i++)
{

aCopy[ i ]=a[ i ];

}

for( i=k=l,j=m+1;i<=m && j<=d;k++){

if(aCopy[ j ] < aCopy[ i ]){

a[ k ]=aCopy[ j ];
j++;

}
else{

a[ k ]=aCopy[ i ];
i++;

}

}

}

​Manja vrednost prepravlja originalni niz a na tekućoj poziciji k za originalni niz. Pomeramo tekuću poziciju onog dela kopije čija je vrednost prepravila originalni niz, kao i tekuću poziciju originalnog niza:

Slika 7: Sortiranje objedinjavanjem. Spajanje manjih u veće nizove-funkcija

​    Manja vrednost prepravlja originalni niz a na tekućoj poziciji k za originalni niz. Pomeramo tekuću poziciju onog dela kopije čija je vrednost prepravila originalni niz, kao i tekuću poziciju originalnog niza:

Slika 8: Sortiranje objedinjavanjem. Spajanje manjih u veće nizove-funkcija- nastavak

​Poredimo članove na tekućim pozicijama levog i desnog dela kopije i sa manjom vrednosti prepravljamo originalni niz na njegovoj tekućoj poziciji .

Slika 9: Sortiranje objedinjavanjem. Spajanje manjih u veće nizove-funkcija- nastavak 2

​Kopiramo dalje preostale elemente, ako ih ima:

Slika 10: Sortiranje objedinjavanjem. Spajanje manjih u veće nizove-funkcija- nastavak premeštanja

Slika 11: Sortiranje objedinjavanjem. Spajanje manjih u veće nizove-funkcija- nastavak premeštanja-shema

​Ako su svi članovi levog niza manji od članova desnog niza  nema razmene. Ako su neki članovi niza desno manji od članova niza levo oni će biti zamenjeni.
Kopiramo dalje preostale elemente, ako ih ima.

---

Glavni deo programa

​U glavnom delu programa treba zadati i rezervisati niz, pozvati metodu razdvajanjeNiza koja dalje pokreće rekurzivni postupak. kada se ona završi, niz je sortiran i posle toga ostaje da se niz prikaže na ekranu:

#include < stdio.h >
void stampajNiz(int a[], int n){

for(int i = 0; i < n; i++)

printf("%d ",a[ i ]);

printf("\n");

}

int main()
{

int n;
int niz[ ]={ 5, 3, 10, -34, 16, 4, 24, 11, -12, 14};
n = sizeof(niz) / sizeof(niz[ 0 ]);

razdvajanjeNiza(niz, 0, n-1, n);
stampajNiz(niz, n);
return 0;

}

Ova metoda je znatno brža od sortiranja zamenom jer je vreme izvršavanja  linearno - logaritamsko T(n)=(n*log(n)) za razliku od sortiranja zamenom  čije je vreme izvšavanja kvadratno

T(n)=n²

---

Sortiranje nizova

---

​Prethodno
​|< Sortiranje nizova

Sledeće
​​Brzo Sortiranje >|