Hallo,
und zwar ist es meine Aufgabe, mergesort umzuändern (aber nur merge() (also ist "a.length/2" eigentlich auch schon falsch, eigentlich müsste dort a.length stehen.)
Ich habe schon ein Programm (vielleicht etwas umständlich geschrieben, welches wenn man z.B. 5 als zufällige Arraygröße eingibt bis zur nächsten Zweierpotenz mit dem höchsten Zufallswert, aber +1) auffült und dies dann auch für die doppelte Länge.
Beispiel:
5 eingegeben, Array von Länge 16 erzeugt. 5 Zahlen random und dann 11 mal die selbe.
Am Ende will ich nur die 5 Zahlen, aber sortiert ausgeben.>
Die merge() Methode soll so umegschrieben werden, dass sich typisch mergesort immer zwei Unterteilungen vergleichen und dann Mischen. Meine Idee:
die Werte vergleiche und in den hinteren Teil (zweite Hälfte nacheinander reinkopieren). Wenn dies sortiert ist, nach vorne kopieren. Dann hat man beispielsweise alle Zweierpäckchen sortiert und ab da sollen es dann Viererpäckchen (Unterteilungen) werden, mein Code funktioniert aber nur für immer zwei aneinanderlegenden zahlen und in der zweiten Hälfte irgendwie gar nicht mehr.
Hat jemand eine Idee wie man das "a.length/2 zu a.length" umändern kann und mein beschriebenes Problem in der merge()-Methode lösen kann?
LG
und zwar ist es meine Aufgabe, mergesort umzuändern (aber nur merge() (also ist "a.length/2" eigentlich auch schon falsch, eigentlich müsste dort a.length stehen.)
Ich habe schon ein Programm (vielleicht etwas umständlich geschrieben, welches wenn man z.B. 5 als zufällige Arraygröße eingibt bis zur nächsten Zweierpotenz mit dem höchsten Zufallswert, aber +1) auffült und dies dann auch für die doppelte Länge.
Beispiel:
5 eingegeben, Array von Länge 16 erzeugt. 5 Zahlen random und dann 11 mal die selbe.
Am Ende will ich nur die 5 Zahlen, aber sortiert ausgeben.>
Die merge() Methode soll so umegschrieben werden, dass sich typisch mergesort immer zwei Unterteilungen vergleichen und dann Mischen. Meine Idee:
die Werte vergleiche und in den hinteren Teil (zweite Hälfte nacheinander reinkopieren). Wenn dies sortiert ist, nach vorne kopieren. Dann hat man beispielsweise alle Zweierpäckchen sortiert und ab da sollen es dann Viererpäckchen (Unterteilungen) werden, mein Code funktioniert aber nur für immer zwei aneinanderlegenden zahlen und in der zweiten Hälfte irgendwie gar nicht mehr.
Hat jemand eine Idee wie man das "a.length/2 zu a.length" umändern kann und mein beschriebenes Problem in der merge()-Methode lösen kann?
LG
Java:
public class Mergesort {
public static int getLength(int n) {
int length = 2;
float x = (float)n;
while (x > 2) {
x = x / 2;
length = length * 2;
}
return length;
}
static void readIn(int[] a, int n) {
for (int i = 0; i < n; i++) {
a[i] = (int) (Math.random() * 100) + 1;
}
int h = 0;
for (int i = 0; i < a.length; i++) {
if (i == 0) {
h = a[i];
} else {
if (a[i] > h) {
h = a[i];
}
}
}
for (int i = n; i < a.length; i++) {
a[i] = h + 1;
}
}
static void mergesort(int[] a) {
int runLength = 1;
while (runLength < a.length/2) {
for (int startRuns = 0; startRuns < a.length/2; startRuns += 2 * runLength) {
merge(a, startRuns, runLength);
}
runLength *= 2;
}
}
static void merge(int[] a, int startRuns, int runLength) {
int i = startRuns;
int j = startRuns + runLength;
while (i < startRuns + runLength && j < startRuns + 2 * runLength) {
if (a[i] > a[j]) {
a[i + a.length / 2] = a[j];
a[i + a.length / 2 + 1] = a[i];
a[i] = a[i + a.length/2];
a[j] = a[i + a.length/2 + 1];
i++;
} else {
a[i + a.length / 2] = a[i];
a[i + a.length / 2 + 1] = a[j];
a[i] = a[i + a.length/2];
a[j] = a[i + a.length/2 + 1];
i++;
}
}
}
public static void main (String[]args){
Out.print("Bitte geben Sie die gewünschte Länge des zufälligen Arrays ein: ");
int n = In.readInt();
int[] a = new int[getLength(n) * 2];
readIn(a, n);
Out.print("nach Sortierung: ");
mergesort(a);
for (int i = 0; i < n; i++) {
Out.print(a[i] + " ");
}
}
}
