Urejanje z zlivanjem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Urejenje z zlivanjem je algoritem za urejanje podatkov v tabeli, in sicer primer algoritma s strategijo DELI in VLADAJ.

Urejanje z zlivanjem deluje po naslednjem principu.
Predpostavimo, da imamo v tabeli n neurejenih elementov in jih želimo urediti od najmanjšega do največjega. Urejanje poteka na zelo preprosti predpostavki.
V fazi deli bomo tabelo razdelili na dva dela enake velikosti (v splošnem se velikosti lahko razlikujeta za največ en element). Dela delimo tako dolgo, dokler v posameznem delu ne dobimo največ dveh elementov (recimo, da je problem takrat majhen), za katera lahko preprosto določimo katero je večje in katero manjše. Na tak način dobimo dve urejeni podtabeli, ki ju moramo združiti v eno urejeno tabelo.
Faza združevanja zahteva kar nekaj dela.
V primerjavi s hitrim urejenjem, imamo pri urejanju z zlivanjem manj dela z delitvijo, več dela pa z združevanjem.



ALGORITEM: uredi z zlivanjem(a,dno,vrh) { if dno < vrh

  s = (dno + vrh) / 2;
  uredi z zlivanjem(a,dno,s);
  uredi z zlivanjem(a,s+1,vrh);
  zlij(a,dno,s,vrh);

}


PRIMER:

Slika:zlivanje.jpg

Glej tudi

Osebna orodja