Mergesort

Vu Wikipedia
Op d'Navigatioun wiesselen Op d'Siche wiesselen
Computer n screen.svg Dësen Informatiksartikel ass eréischt just eng Skizz. Wann Dir méi iwwer dëst Thema wësst, sidd Dir häerzlech invitéiert, aus dëse puer Sätz e richtegen Artikel ze schreiwen. Wann Dir beim Schreiwen Hëllef braucht, da luusst bis an d'FAQ eran.

Mergesort ass ee séiert allgemengt Zortéierverfahren, dat 1945 vum John von Neumann virgestallt ginn ass. Et handelt sech em ee rekursivt, stabilt awer net in-place Zortéierverfahren, dat nom Divide and Conquer-Prinzip schafft.

Funktiounsweis[änneren | Quelltext änneren]

Mergesort ass eng speziell Uwennung von enger allgemenger Virgehensweis fir rekursiv Algorithmen.

D'Prinzip vun Divide and Counquer huet dräi Schrëtt:

  1. Divide: De Problem gëtt an eng Zuel vu gläichgroussen Deelproblemer zerluecht.
  2. Conquer: Deelproblemer ginn duerch Rekursioun (duerch Opruff vum selwechten Algorithmus) geléist.
  3. Combine: Déi eenzel Léisunge ginn zu enger Gesamtléisung vum Originalproblem nees zesummegesat. Hei gëtt déi eigentlech Aarbecht gemaach.

Bei Mergesort bedeit dëst:

  1. Divide: Mergesort spléckt een Tableau vun Elementer, déi zortéiert solle ginn, an zwéin Deeler vun der Gréisst op.
  2. Conquer: Déi zwéin Deeltableaue gi rekursiv mat Mergesort zortéiert.
  3. Combine: Merge mëscht déi zwéin zortéiert Deeltableauen, soudatt s'eng zortéiert Sequenz erginn.

Algorithmus[änneren | Quelltext änneren]

De folgende Pseudocode stellt eng Implementéierung vum Algorithmus dur:

Mergesort(A,p,r)
	if p<r then
		q:= (p+r)/2
		Mergesort(A,p,q)
		Mergesort(A,q+1,r)
		Merge(A,p,q,r)
	fi
end

Prozedur Merge

Merge(A,p,q,r)
	i:= p
	j:= q+1
	k:= p
	while i<=m and j<=r do
		if A[i]<A[j] then
			B[k]:= A[i]
			i:= i+1
		else
			B[k]:= A[j]
			j:= j+1
		fi
		k:= k+1
	od

	while i<=m do
		B[k]:= A[i]
		i:= i+1
		k:= k+1
	od

	while j<=r do
		B[k]:= A[j]
		j:= j+1
		k:= k+1
	od

	// Kopéiere vum Tableau B nees an den Tableau A
	for i:=p to r do
		A[i]:= B[i]
	od
end

Lafzäit[änneren | Quelltext änneren]

Literatur[änneren | Quelltext änneren]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990.