| | |
| Titel: | Sortieralgorithmen | |
| Startseite english | ||
| ||
| |<< Anfang < Zurück Index Weiter > Ende >>| | |  |
Sortierdauer
Merge Sort (Sortieren durch Mischen)
Beschreibung
- Das Verfahren arbeitet rekursiv nach dem Divide & Conquer[1] – Prinzip.
- Die Folge wird rekursiv bis zur trivilaen Teilfolge der Länge 1 zerteilt (Divide).
- Diese Teilfolgen werden jeweils durch Merging vereint, die vereinten wiederum. etc. bis zur sortierten Gesamfolge (Conquer).
- Es wird ein zusätzliches Hilfsfeld Ziel von der gleichen Größe wie die zu sortierende Gesamtfolge benötigt.
Programmcode
procedure MergeSort ( var f : TArray;
HighIndex : integer ) : string;
var Ziel : TArray; //
Hilfsfeld zum Einsortieren für die Procedure Merge
procedure Merge ( links, mitte,
rechts : integer );
var h, i, j, k :
integer;
begin
i := links; //
Index des linken Teilfeldes
j := mitte + 1; //
Index des rechten Teilfeldes
k := links; //
Index des (sortierten) Hilfsfeldes
repeat
if f[i] <
f[j]
then begin ziel[k] :=
f[i]; inc (i); end
else begin ziel[k] :=
f[j]; inc (j); end;
inc
(k);
until (i > mitte) or (j
> rechts);
if i >
mitte
then for h := j to rechts do
ziel [k+h-j] := f[h]
else for h := i to mitte do
ziel [k+h-i] := f[h];
for h := links to rechts do
f[h] := Ziel [h]; // zurückkopieren ins Datenfeld
end; // subproc
Merge
procedure rMergeSort (links,
rechts : integer);
// rekursiver Teil des
MergeSorts
var mitte :
integer;
begin
if links <
rechts
then
begin
mitte := (links + rechts)
div 2;
rMergeSort (links ,
mitte ); // sortieren des linken Teils
rMergeSort (mitte+1 ,
rechts); // sortieren des rechten Teils
Merge (links, mitte,
rechts); // zusammenmischen der beiden Teile
end;
end; // SubProc
MergeSort
begin //
MergeSort
rMergeSort (0,
HighIndex);
end; //
MergeSort
Zurück zu Themenseiten:
StudyPaper.com/Startseite/Computer/Informatik
StudyPaper.com/Startseite/Wissenschaft/Wirtschaftswissenschaften
StudyPaper.com/Startseite
Das Setzen von Verweisen (Links) auf diese Seite ist gestattet und bedarf keine vorherige Absprache.
