Computer n screen.svg Dësen Informatiksartikel ass eréischt just eng Skizz. Wann Dir méi iwwer dëst Theema 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

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

De follgende 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

LiteraturÄnneren

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