mergeSort

[germandute]

Hallo erstmal, das ist mein erster Post in einem Forum seit ner langen Zeit, also bitte entschuldigt wenn es etwas ungenau ist

Also folgendes Problem.

Ich hab zwei sortierte Felder

feldA = {1,3,5,9}
feldB = {2,4,6,10}

Nun ist die Aufgabe diese beiden Felder zu einem einzelnen sortierten Array mittels Merge-Sort (selbst-
implementiert, die Sortierung erfolgt beim Zusammenf¨ugen und nicht separat)

Also ich muss sozusagen bei dem verschmelzen Punkt des MergeSort Algorithmus ansetzen. Folgende Ideen hab ich schon gehabt.

1) Beide Arrays durchgehen, also feldA und überprüfen ob in beiden ein kleinere Wert ist, wenn ja dann in das neue Feld eintragen (wobei ich aber das problem habe das der kleiner Wert noch in den beiden Feldern drin bleibt, was bei einem weiteren durchlauf wieder als kleinere Wert vorkommt - also müsste man den Wert dann irgendwie entfernen (was bei arrays glaub nicht so einfach ist).

2) den ersten Wert in das neue Feld dann den zweiten und dann schaun ob der erste Wert kleiner ist als der andere, das solange bis feldA und feldB abgearbeitet sind, wobei ich mir aber nicht sicher bin ob das dann noch als MergeSort durchgeht.

Also am liebsten wäre mir die erste Variante, aber wiegesagt ich habe keine ahnung wie man ein Element aus einem Array löscht/entfernt.

Ich gebe zu ich bin etwas spät dran mit der Aufgabe (muss morgen fertig sein, aber das ist der letzte knackpunkt). Im Moment bin ich halt im Umzugsstress...also ich hoffe ihr rettet mir den Hintern

Viele Grüße und ein großes Danke schonmal von mir.

 

[Final_Striker]

du musst keine werte löschen, es reicht einfach wenn du dir merkst wo du dich befindest. D.h. wenn du die 1 aus dem feld a in das neue array geschrieben hast musst du dir merken das du jetzt in dem feld a auf dem Element 1 in dem Fall der 3 stehst.

 

[germandute]

Sorry, verstehe ich nicht

kannst das vll mal bissle ander schreiben...

was meinst du mit merken wo du bist?

 

[Landei]

Mal aus'm Kopp:

public int[] merge(int[] a, int[] b) {
  int[] c = new int[a.length + b.length];
  int aIndex = 0;
  int bIndex = 0;
  while(aIndex + bIndex < c.length) {
     c[aIndex + bIndex] = (aIndex == a.length 
        || (bIndex < b.length && a[aIndex] > b[bIndex]))  
        ? b[bIndex++] : a[aIndex++];
  }
  return c;
}

 

[germandute]

Ui Danke,
hast en super "Kopp" haut hin.
aber noch eine letzte Frage. Wie rufe ich die Methode auf?

habs grad nur mitten im Quelltext probiert...

und schonmal danke fürs Retten

 

[nrg]

anhand von deinem post so zb:

int[] rueckgabeVonDerMethode = merge(feldA, feldB);

dann haste dein zusammengesetztes Array in dem int[]-arrray namens rueckgabeVonDerMethode stehen.

grüße

edit: methode merge sollte dazu noch statisch sein