2 Sortierte Teil-Arrays verbinden (Merge Sort)

[kita]

Hi,

ich suche einen Algorithmus, womit man 2 sortierte Teil-Arrays zu 1nem sortierten Array machen kann ohne zusätzlichen speicher zu verwenden.

beispiel (Java):

int[] A = {11,13,15,17,

10,12,14,16};

soll später:

A = {10,11,12,13,

14,15,16,17};

sein.

Normalerweise legt der Mergesort dafür ein neues tmp-Array mit der länge des alten Arrays an und kopiert alle elemente sortiert in das tmp-Array danach wieder in das Ursprungs-Array zurück.

Ich suche jetzt ne möglichkeit das mergen ohne extra Speicher zu machen, ich habe im internet auch einiges gefunden nur war das nie vollständig.

mfg kita

[Crash2001]

Ohne zusätzlichen Speicher (zumnindest temporär) zu verwenden halte ich das für nicht lösbar. Irgendwohin muss man ja beim sortieren auslagern... Mindestens ein Feld muss man definitiv zwischenspeichern - und das braucht Platz.

[Klotzkopp]

Vermutlich ist hier nicht gemeint, das ganz ohne zusätzlichen Speicher zu lösen, sondern mit konstantem Speicherbedarf, und nicht mit linearem, wie ihn Mergesort normalerweise hat.

Die C++-Standardbibliothek hat dafür eine Funktion: std::inplace_merge.

Da das eine Templatefunktion ist, kann man sich die Implementierung bei jedem Compiler einfach ansehen. Vielleicht findet man da ein paar Anregungen.

[kooghelmut]

Muß die Sache unbedingt im Speicher gelöst werden?

Warum nicht so?

1. Beide Tabellen mischen in eine Datei.

2. Tabelle löschen.

3. Datei in Tabelle laden.

Freundliche Grüße

Koog, Helmut

[AndiE]

So ganz verstehe ich de Aufgabe nicht.

Wenn

int A[4] = {11,13,15,17};

int B[4]= { 10,12,14,16};

dann "muss" doch

int C[8]=merge(A,= {10,11,12,13,

14,15,16,17};

sein.

MfG

André

[Klotzkopp]

Richtig, aber dafür braucht Mergesort eben ein Zielarray, das genauso groß sein muss wie die beiden Quellarrays. Mergesort arbeitet nicht "in-place", sondern braucht zusätzlichen Speicher in Größe der zu sortierenden Sequenz. Die Frage hier ist, wie das ohne geht.

[kooghelmut]

Ist nicht mein Thema, ich habe nur geantwortet. Bitte schauen Sie nach unter "kita".

Tschüs

Helmut Koog

[Klotzkopp]

Ist nicht mein Thema, ich habe nur geantwortet.

AndiE hat auch nur geantwortet, das war nicht auf dich bezogen.

In Webforen ist es übrigens sehr unüblich, sich zu siezen. Das macht einen sehr gestelzten Eindruck.

[AndiE]

Hallo,

ich denke, dass die Aufgabenstellung so nicht möglich ist.

ich habe das Prinzip vom "merge" so verstanden:

Wenn F ein Array mit den sortierten Namen der Frühschicht und S ein Array mit den sortierten Namen der Spätschicht sei, dann kann ich mit "merge" ein Array B für die sortierten Namen der Belegschaft erzeugen.

B=merge(F,S);

Dabei werden die Daten aus den beiden anderen "Quell"-Arrays nach ihrem Wert in das neue "Ziel"-Array eingefügt.

Nach dem "merge" existieren drei Arrays, deren Daten sich je nach Anwendungsfall unterscheiden.

Ähnlich ist es z.B. bei Inventaren.

Wenn die Abteilungen ihre Inventare aufnehmen, kann ich sie mit merge zu einem Gesamtinventar zusammenführen, aber die Einzelinventare bleiben für sich doch bestehen.

LG

André

[Klotzkopp]

Stell es dir einfach so vor, dass du ein Array mit zwei aufeinanderfolgenden, in sich sortierten Sequenzen hast, wie in dem Beispiel im ersten Beitrag.

Dieses Array willst du nun "in-place", also ohne ein zweites Array, sortieren. Das geht natürlich mit jedem Sortieralgorithmus, der nur konstanten Speicherbedarf hat, aber die Information über die Struktur der Daten würde eigentlich eine Sortierung in linear Zeit erlauben, indem man einfach den letzten Schritt des Mergesort durchführt.

Es gibt auch eine "in-place"-Variante von Mergesort, allerdings ist die dann nicht mehr stabil.

[AndiE]

Ok,

ich habe überlegt, dass es zwei Extreme gibt:

a) 15,16,17,18,11,12,13,14

und

11,13,15,17,12,14,16,18

in a)

Das Minimum von Teilliste A ist größer als das Maximum von Teilliste B.

Das Maximum von Teilliste B ist kleiner als das Minimum von Teilliste A.

->der Bereich der Listen liegt nebeneinander.

in

Das Minimum von Teilliste A ist kleiner als das Maximum von Teilliste B

Das Maximum von Teilliste B ist größer als das Maximum von Teilliste A

-> der Bereich der Listen liegt übereinander

Lösung:

in a)

vertausche die Stellen:

5 und 1

(Lade 5 in M1, lade 1 in 5, lade M1 in 1)

6 und 2

7 und 3

8 und 4

->in-place OK

in

lasse 1(11)

merke 2 als M1(13)

setze 5 auf 2 (12)

merke 3 als M2(15)

setze M1 auf 3 (13)

merke 4 als M1 (17)

setze 6 auf 4 (14)

setze M2 auf 5(15)

setze 7 auf 6 (16)

setze M1 auf 7

lasse 8(18)

-> das bedeutet, theoretisch käme man mit zwei Merkvariablen(M1 und M2) aus.

fast in-place(??)

Die Frage ist nun,

a)wie man das in Anweisungen umwandelt, und

b)die Fälle zwischen a) und unterscheidet.

LG

André

[gelang(while)t]

laufe deinen Array solange durch, bis du merkst das die stelle > stelle[i+1] (währendessen Zähler mitlaufen lassen um den Index herauszufinden)...anschließend fängst du wieder bei zahl[0] an und hängst sie ans Ende des Arrays...das wiederholst du so lange, bis deine Indexzahl deiner Zählerzahl entspricht, dann hast du den Array theoretisch sortiert ohne einen 2ten anzulegen^^

[gelang(while)t]

sorry, hab noch enn logischen Fehler drin...aber der Ansatz ist gut^^