Algorithmen und Berechnungshomplexität7 Präsenzblatt I
Aufgabe
Gegeben : Ein unsortiertes Array 8 ,1, 5, 3 , 4 , 9 6 5 , 8
, ,
Um das
Array mithilfe von MergeSort zu sortieren ,
Array zusachst lange geteilt
wird das
gegebene so ,
bis die einzelnen Teilarrays eine
Lange von 1 haben ,
Anschließend werden diese Teilarrays rekursiv in
sortierter Reihenfolge wieder zusammengeführt .
Formel verwendet,
Dabei wird die
folgen de
um die Mitte eines Arrays zu berechnen, me tr
Hierbei ist I der Start- und r der Endindex des aktuell betrachteten Teilarrays ,
, 815349658
Index : 0 12345678
Beispiel :
815349658
m = 0+
4
-0 = 2
815349658
815349658
81
18
158346958
134585689
134556889
Das sortierte Array lautet 1 , 3 , 4 , 5 , 5 6 8 8 , 9 , , .