Startseite
Informatik
Algorithmen
Sortieren
BucketSort
RadixSort
QuickSort
DRUCK
2004
2005
2006
2007
2008
2009
MergeSort
HeapSort
BubbleSort
SelectionSort
InsertionSort
SlowSort
BogoSort
Komprimieren
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
MergeSort
Ein relevanter Algorithmus zum externen Sortieren ist der MergeSort!
Ein relevanter Algorithmus zum externen Sortieren ist der MergeSort!
Einführung
Theorie: MergeSort
Definition
Der
MergeSort
ist das Gegenstück zum
QuickSort.
Hier wird in gleich große Teile zerlegt, die wesentliche Arbeit aber erst bei der Komposition geleistet:
Die Liste wird in der Mitte geteilt, beide Hälften werden rekursiv sortiert und die Ergebnislisten geordnet
zusammengemischt.
[FUNPROG]
Die Operation „mische” bzw. „merge” fügt zwei sortierte Listen zu einer einzigen sortierten Liste zusammen.
Die Operation „mische” bzw. „merge” fügt zwei sortierte Listen zu einer einzigen sortierten Liste zusammen.
Komplexität
Hier erhalten wir einen Aufwand in der Größenordnung
O(n log n).
Dieser Aufwand wird sogar immer garantiert, da bei der Zerlegung grundsätzlich die Längen der Listen halbiert werden.
[FUNPROG]
Der Rumpf der Funktion enthält aber mehr Operationen als der von QuickSort, weshalb QuickSort — im Durchschnitt — etwas schneller ist.
Der Rumpf der Funktion enthält aber mehr Operationen als der von QuickSort, weshalb QuickSort — im Durchschnitt — etwas schneller ist.
Konkretes Zahlenbeispiel
Dabei sei nun
[9,6,2,8,4,7,3,5,1]
die zu sortierende Liste:
[9,6,2,8,4,7,3,5,1]([9,6,2,8][4,7,3,5,1])(([9,6][2,8])([4,7][3,5,1]))((([9][6])([2][8]))(([4][7])([3][5,1])))((([9][6])([2][8]))(([4][7])([3]([5][1]))))((([9][6])([2][8]))(([4][7])([3][1,5])))(([6,9][2,8])([4,7][1,3,5]))([2,6,8,9][1,3,4,5,7])[1,2,3,4,5,6,7,8,9]
Implementierung
Implementierung des MergeSort
Prolog-Algorithmen sind von ihrer Natur her recht kurz,
so auch die Prolog-Implementierung zu MergeSort.
Implementierung mit Prolog
% ?-mergesort([9, 6, 2, 8, 4, 7, 3, 5, 1], SL).
mergesort([], []).
mergesort([X], [X]).
mergesort(L, SL) :-
divide(L, L1, L2),
mergesort(L1, SL1),
mergesort(L2, SL2),
merge_(SL1, SL2, SL), !.
divide([], [], []).
divide([X], [X], []).
divide([X, Y|L], [X|L1], [Y|L2]) :- divide(L, L1, L2).
merge_([], SL, SL).
merge_(SL, [], SL).
merge_([X|SL1], [Y|SL2], [X|SL]) :- X < Y, merge_(SL1, [Y|SL2], SL).
merge_([X|SL1], [Y|SL2], [Y|SL]) :- not(X < Y), merge_([X|SL1], SL2, SL).
Implementierung mit SML
(* count: Hilfsfunktion
zählt die Elemente gegebener Liste *)
fun count nil = 0
| count (x::xl) = 1 + count xl;
(* low: Hilfsfunktion
gibt die ersten cnt Elemente als Liste zurück. *)
fun low 0 xl = nil
| low cnt nil = nil
| low cnt (x::xl) = x :: low (cnt-1) xl;
(* high: Hilfsfunktion
das Komplement zu low. *)
fun high 0 xl = xl
| high cnt nil = nil
| high cnt (x::xl) = high (cnt-1) xl;
(* merge: Hilfsfunktion
mischt zwei vorsortierte Listen unter Einhaltung der Ordnung
zu einer einzigen Liste zusammen. *)
fun merge nil nil = nil
| merge nil yl = yl
| merge xl nil = xl
| merge (x::xl) (y::yl) =
if (x < y)
then x :: (merge xl (y::yl))
else y :: (merge (x::xl) yl);
(* mergesort: klar!
half: Anzahl der Hälfte der Elemente der Liste.
lower: Erste Hälfte der Liste.
higher: Zweite Hälfte der Liste. *)
fun mergesort nil = nil
| mergesort (x::nil) = [x]
| mergesort el =
let
val half = (count el) div 2;
val lower = low half el;
val higher = high half el;
in (* Merge 2 sortierte Listen! *)
merge (mergesort lower) (mergesort higher)
end;
Implementierung mit Perl
#!/usr/bin/perl
sub MergeSort {
my($comp,$s1,$e1,$s2,$e2,@A) = @_;
my $i = $s1;
my $j = $s2;
my ($k,$a);
my @tmp; # Hilfsarray
if ($s1 < $e1) {
@A = &MergeSort($comp,$s1,int(($e1+$s1-1)/2),int(($e1+$s1+1)/2),$e1,@A);
};
if ($s2 < $e2) {
@A = &MergeSort($comp,$s2,int(($e2+$s2-1)/2),int(($e2+$s2+1)/2),$e2,@A);
};
for ($k=0; $k<=($e1-$s1+$e2-$s2+1); $k++) {
if (((($i<=$e1) && ($j<=$e2)) && (&$comp($A[$i],$A[$j]))) || (($i<=$e1) && ($j>$e2))) {
$tmp[$k] = $A[$i++];
}
else {
$tmp[$k] = $A[$j++];
};
};
for ($a=0; $a<=($e1-$s1+$e2-$s2+1); $a++) {
$A[$s1+$a] = $tmp[$a];
};
return @A;
}; # sub MergeSort...
# --- Anwendungsbeispiel ---
# Vergleichsfunktionen
my $numAsc = sub {return $_[0] < $_[1];};
my $numDesc = sub {return $_[0] > $_[1];};
@A = (4,2,9,3,0,5,1,8,6,7);
my $s1 = 0;
my $e1 = int(($#A / 2) - 1);
my $s2 = int($#A / 2);
my $e2 = ($#A);
@B = &MergeSort($numAsc,$s1,$e1,$s2,$e2,@A);
@C = &MergeSort($numDesc,$s1,$e1,$s2,$e2,@A);
print "# @A (unsortiert)\n";
print "#\n";
print "# @B (aufsteigend; asc)\n";
print "# @C (absteigend; desc)\n";
exit;
Implementierung mit Delphi
unit UMergeSort;
interface
procedure MergeSort(var A: array of Integer);
implementation
procedure MergeSort(var A: array of Integer);
(* Es werden zwei sortierten Bereiche des Arrays ineinander gemergt. *)
procedure Merge(LoL, HiL, LoR, HiR: Integer);
var
SA: array of Integer; // Hilfsarray: die 2 Bereiche werden hier reingemergt!
SI: Integer; // Index für das Hilfsarray
IL, IR: Integer; // Lauf-Indezes der beiden Teilbereiche
begin
// Initialisierung
// Das Hilfsarray SA mit der Länge beider Bereiche
SetLength(SA, (HiL - LoL + 1) + (HiR - LoR + 1));
// Die Laufvariablen beginnen jeweils mit dem niederwertigen Bereichsindex.
IL := LoL;
IR := LoR;
// Der eigentliche Merge-Vorgang!
for SI := Low(SA) to High(SA) do
begin
// Haben beide Bereiche noch Elemente?
if ((IL <= HiL) and (IR <= HiR)) then
begin
if (A[IL] < A[IR]) then
begin
SA[SI] := A[IL];
Inc(IL);
end
else
begin
SA[SI] := A[IR];
Inc(IR);
end;
end
// Andernfalls: Hat der linke Bereich noch Elemente?
else if (IL <= HiL) then
begin
SA[SI] := A[IL];
Inc(IL);
end
// Andernfalls: Hat der rechte Bereich noch Elemente?
else if (IR <= HiR) then
begin
SA[SI] := A[IR];
Inc(IR);
end;
// Andernfalls: Beide Breiche sind schon abgearbeitet!
// Dieser Fall kommt aber nicht innerhalb dieser Schleife nicht zustande!
end;
// Finalisierung: SA wird wieder in die zwei Bereiche zurückkopiert!
SI := Low(SA);
for IL := LoL to HiL do
begin
A[IL] := SA[SI];
Inc(SI);
end;
for IR := LoR to HiR do
begin
A[IR] := SA[SI];
Inc(SI);
end;
end;
(* Der MergeSort mit den Bereichsgrenzen *)
procedure MSort(Lo, Hi: Integer);
var
Middle: Integer;
begin
if (Lo < Hi) then
begin
Middle := (Lo + Hi) div 2;
MSort(Lo, Middle); // Linker Bereich wird sortiert
MSort(Middle + 1, Hi); // Rechter Bereich wird sortiert
// Die zwei sortierten Bereiche werden ineinander gemergt!
Merge(Lo, Middle, Middle + 1, Hi);
end;
end;
begin
MSort(Low(A), High(A));
end;
end.
Implementierung mit C++
#include <stdlib.h>
#include <cstdio>
void mergesort(int *l, int s1, int e1, int s2, int e2) {
//printf(" mergesort(..., %d, %d, %d, %d) \n", s1, e1, s2, e2);
int i = s1, j = s2, k;
int *list2;
if (s1 < e1) mergesort(l, s1, ((e1 + s1 - 1) / 2), (e1 + s1 + 1) / 2, e1);
if (s2 < e2) mergesort(l, s2, ((e2 + s2 - 1) / 2), (e2 + s2 + 1) / 2, e2);
for (k = 0; k <= (e1 - s1 + e2 - s2 + 1); k++) {
if ((((i <= e1) && (j <= e2)) && (l[i] < l[j])) || ((i <= e1) && (j > e2)))
list2[k] = l[i++];
else list2[k] = l[j++];
}
for (int a = 0; a < (e1 - s1 + e2 - s2 + 2); a++) l[s1 + a] = list2[a];
}
// Test: mergesort
int main() {
int list[] = {10, 5, 3, 12, 1, 9, 4};
int listSize = sizeof(list) / sizeof(*list);
mergesort(list, 0, ((listSize / 2) - 1), (listSize / 2), (listSize - 1));
printf("...And the sorted list looks now like :\n");
for(int i = 0; i < listSize; i++)
printf("list[%d]=%d \n", i, list[i]);
system("PAUSE");
return 0;
}