Merge sort

[marija]

Može li neka dobra duša napisati algoritam za sortiranje niza pomoću merge sorta please!

[ahri]

moze.
dakle, algoritam:

funkcija mergesort:
"ako u nizu imas vise od jednog elementa, podijeli ga na 2 dijela i sortiraj svaki posebno, te ih onda spoji funkcijom merge"
funkcija merge (od 2 niza):
"stavi i=0, j=0. pogledaj je li a[i] manji od b[j]. ako je, strpaj u novi niz a[i] te povecaj i za jedan. ako nije, strpaj b[j] i povecaj j za 1. to radi sve dok jedan od nizova ne bude prazan, i onda strpaj ostatak drugog niza u novi niz".


sad malo objasnjenja.

dakle, ako imas jedan element, on je ocito sortiran.
a ako ih imas vise... onda ces sortirani niz dobiti tako da spojis dvije sortirane polovice u jedan (sortirani) niz.
te dvije sortirane polovice ces dobiti tako da svaki od nizova sortiras... naravno, rekurzivnim pozivom funkcije :).

merge bi trebao biti jasan.
evo neki primjer.

58 17 34 92 23 5 88 69


1) dakle, prvo se pozove merge za cijeli niz.
elemenata ima vise od 1, dakle podijelis popola.
2a) krenemo u ljevu polovicu
58 17 34 92

ponovo ima elemenata vise od 1, podijelimo popola

3a) 58 17

ponovo ima vise od 1, podijelimo popola

4a) 58
tu je sad 1, on je sortiran.
4b) druga polovica je 17.
ona je isto sortirana
sad ih "spojimo".
dobijemo 17 58.

sad druga polovica od 3 koraka
3b) 34 92
4c) 34
4d) 92
spojimo, dobijemo 34 92
sad spojimo 3a i 3b
17 34 58 92

sad desna polovica drugog koraka
2b) 23 5 88 69
3c) 23 5
4e) 23
4f) 5
spojimo : 5 23
3d) 88 69
4g) 88
4h) 69
spojimo: 69 88
spojimo 3c) i 3d)
5 23 69 88

i sad spojimo 2a) i 2b)
5 17 23 34 58 69 88 92


i niz je sortiran :).

ako zelis, mozes dobiti i ovakav grafikon: :)

58 17 34 92 23 5 88 69
58 17 34 92 23 5 88 69
58 17 34 92 23 5 88 69
58 17 34 92 23 5 88 69
58 17 34 92 23 5 88 69
17 58 34 92 23 5 88 69
17 5834 92 23 5 88 69
17 58 34 92 23 5 88 69
17 58 34 92 23 5 88 69
17 58 34 92 23 5 88 69
17 58 34 92 23 5 88 69
17 34 58 92 23 5 88 69

itd itd...

_________________

[ahri]

[Gost]

Fala! Fala!

[ahri]

nema na cemu :)

_________________