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:
Pretpostavimo da imamo sledeći niz koji je potrebno sortirati u rastućem redosledu:
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:
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.
Deljenje niza na manje podnizove
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:
Metoda koja to radi bi bila:
void razdvajanjeNiza(int a[], int l,int d,int n)
{
{
int m=(l+d)/2;
if(l < d)
{
return;
}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
}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:
Funkcija koja vrši razdvajanje:
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:
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:
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++)
{
}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:
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++)
{
}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 ]){
else{
}
a[ k ]=aCopy[ j ];
j++;
}j++;
else{
a[ k ]=aCopy[ i ];
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:
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:
Poredimo članove na tekućim pozicijama levog i desnog dela kopije i sa manjom vrednosti prepravljamo originalni niz na njegovoj tekućoj poziciji .
Kopiramo dalje preostale elemente, ako ih ima:
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.
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){
int main()
{
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;
}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)=n2
Sledeće
Brzo Sortiranje >| |