Hallo Forengemeinde,
ich soll MergeSort rekursiv programmieren. Die Methodensignatur darf dabei nicht verändert werden.
Mein geschriebender Code kann mit einem Array a[7 5 3 1] momentan:
Schritt 1:
b [7 5] #### e[3 1]
Erneuter Methodenaufruf mit b
Schritt2
b[7] #### e[5] ####
merge
c[5 7]
Das Zurückspringen auf Stelle 1 klappt nicht um die Methode auch mit e auszuführen.
Habt ihr einen Tipp für mich?
Hinweis:
Ich lerne momentan die Java Algorithmen und habe erst im nächsten Jahr Objektorientierte Programmierung.
import AlgoTools.IO; = Uni interne Klasse zum einlesen und ausgeben
ich soll MergeSort rekursiv programmieren. Die Methodensignatur darf dabei nicht verändert werden.
Mein geschriebender Code kann mit einem Array a[7 5 3 1] momentan:
Schritt 1:
b [7 5] #### e[3 1]
Erneuter Methodenaufruf mit b
Schritt2
b[7] #### e[5] ####
merge
c[5 7]
Das Zurückspringen auf Stelle 1 klappt nicht um die Methode auch mit e auszuführen.
Habt ihr einen Tipp für mich?
Hinweis:
Ich lerne momentan die Java Algorithmen und habe erst im nächsten Jahr Objektorientierte Programmierung.
import AlgoTools.IO; = Uni interne Klasse zum einlesen und ausgeben
Java:
import AlgoTools.IO;
public class MergeSort {
private static int schritte = 0;
public static void main(String[] args) {
int laenge = 0;
int []d;
// Lese Array ein
do {
laenge = IO.readInt("Laenge des Array: ");
} while(laenge <= 0);
// Lege Array an, welches ausgegeben wird
int[]a= new int[laenge];
// lies Zeile mit korrekter Anzahl von Buchstaben ein
do {
a = IO.readInts("Bitte Zahlenfolge eingeben ");
} while(a.length != laenge);
d = sortRekursiv(a);
for (int i = 0;i < d.length;i++) {
IO.print(d[i]);
} // end of for
}
//Array immer in zwei haelften Teilen bis nur noch Arrays mit zweit Zahlen Uebrig bleiben
//Dann Teilstücke sortieren und zusammensetzen
public static int[] sortRekursiv(int[] a) {
//Array teilen
//Teilarray b anlegen
int[]b = new int[(a.length/2)];
if (a.length%2 == 1) { // Wenn Rest von a ungerade ist
//Teilarray e anlegen
int[]e = new int[((a.length/2)+1)];
IO.println("Länge b "+b.length);
IO.println("Länge c "+e.length);
//Daten kopieren
//a kopieren in b
for (int i = 0; i< b.length ;i++ ) {
b[i] = a[i];
} // end of for
IO.print("Array b ");
for (int i =0;i<b.length ;i++ ) {
IO.print(b[i]);
} // end of for
IO.println();
//a kopieren in e
for (int i = 0, j = (b.length); i < e.length|| j < a.length;i++, j++ ) {
e[i] = a[j];
}
IO.print("Array e ");
for (int i =0;i<e.length ;i++ ) {
IO.print(e[i]);
} // end of for
IO.println();
if (b.length == 1 && e.length == 1) {// Größe der Teilstücke 1
return merge (b,e); //Sortier beide Teilstücke zu einem Array
} else {
if (b.length > 1){ // Wenn Teilstück b noch größer 1
return sortRekursiv(b);
} else { // Wenn Teilstück c noch größer 1
//throw new RuntimeException("Überprüfung");
return sortRekursiv(e);
}
}
} else { // Wenn Rest von e gerade ist
//Teilarray c anlegen
int[]e = new int[((a.length/2))];
IO.println("Länge b "+b.length);
IO.println("Länge e "+e.length);
//Daten kopieren
//a kopieren in b
for (int i = 0; i< b.length ;i++ ) {
b[i] = a[i];
} // end of for
IO.print("Array b ");
for (int i =0;i<b.length ;i++ ) {
IO.print(b[i]);
} // end of for
IO.println();
//a kopieren in e
for (int i = 0, j = (b.length); i < e.length || j < a.length;i++, j++ ) {
e[i] = a[j];
}
IO.print("Array e ");
for (int i =0;i<e.length ;i++ ) {
IO.print(e[i]);
} // end of for
IO.println();
schritte = schritte +1;
if (b.length == 1 && e.length == 1) { // Größe der Teilstücke 1
return merge (b,e); //Sortier beide Teilstücke zu einem Array
} else {
if (b.length > 1){ // Wenn Teilstück b noch größer 1
return sortRekursiv(b);
} else { // Wenn Teilstück e noch größer 1
//throw new RuntimeException("Überprüfung");
return sortRekursiv(e);
}
}
} // end of if-else
}
public static int[] merge (int[]a, int[]b) { // mischt a und b
// liefert Ergebnis zurueck
int i=0, j=0, k=0; // Laufindizes
int[] c = new int[a.length + b.length]; // Platz fuer Folge c besorgen
while ((i<a.length) && (j<b.length)) { // mischen, bis ein Array leer
if (a[i] < b[j]) // jeweils das kleinere Element
c[k++] = a[i++]; // wird nach c uebernommen
else
c[k++] = b[j++];
}
while (i<a.length) c[k++] = a[i++]; // ggf.: Rest von Folge a
while (j<b.length) c[k++] = b[j++]; // ggf.: Rest von Folge b
return c; // Ergebnis abliefern
}
}
Zuletzt bearbeitet: