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.
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)
{
Rekurzivni postupak razdvajanja bi se slikovito mogao prikazati:{
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;
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)
{
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.{
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];
}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)
{
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:{
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++;
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
|
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()
{
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 kvadratnovoid 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;
T(n)=n2
| Prethodno |< Sortiranje nizova |
Sledeće Brzo Sortiranje>| |