Funktion mittels Rekursion: sortMerge(n,a)
-
Hallo,
ich habe folgende Aufgabe bekommen:
Es soll eine Funktion erstellt werden, welche Arrays mit dem Verfahren „Sortieren durch
Mischen“ aufsteigend sortiert.
Funktion mittels Rekursion: sortMerge(n,a)
Dabei wird wie folgt vorgegangen:
Falls a maximal ein Element enthält ist man fertig (bereits sortiert)
Ansonsten
Erzeuge 2 passende Arrays b und c
Bilde 2 Hälften des Arrays a und speichere sie in die neuen Arrays b und c
Hinweis:
ein neues Array mit Namen h und m Elementen lässt sich wie folgt erzeugen:
double *h = new double[m];
Der Typ ist hier double; andere Typen analog;
m ist ein Ausdruck/eine Variable vom Typ int.
Mit delete []h kann man es wieder löschen.
Sortiere b und c mit SortMerge
Mische b und c und speichere das Ergebnis in a
Lösche b und cBislang habe ich folgendes Programm dazu erstellt:
void sortMerge(int n, int *a){ void merge(int *a1, int l1, int *a2, int l2); if (n>1){ sortMerge(n/2, a); sortMerge((n+1) / 2, a + n / 2); merge(a, n/2, a + n/2, (n+1) / 2); } } void merge(int *a1, int l1, int *a2, int l2){ int p1 = 0, p2 = 0; int temparray[10]; for (int i = 0; i < l1 + l2; i++){ if (p1 == l1) temparray[i] = a2[p2++]; else if (p2 == l2) temparray[i] = a1[p1++]; else if (a1[p1] > a2[p2]) temparray[i] = a2[p2++]; else temparray[i] = a1[p1++]; } for (int i = 0; i < l1; i++) a1[i] = temparray[i]; for (int i = l1; i < l1 + l2; i++) a2[i-l1] = temparray[i]; }Ich glaube nur leider, dass das so nicht ganz gewollt war.
Allerdings weiß ich auch nicht, wie das in der Aufgabenstellung wirklich gemeint war.Kann mir hierbei bitte jemand helfen?
-
Falsches Forum, das gehört ins C++ Forum.
-
Dieser Thread wurde von Moderator/in Jochen Kalmbach aus dem Forum C++/CLI mit .NET in das Forum C++ (auch C++0x) verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Woher kommt die Größe 10 für temparray?
Überhaupt: Kannst du deine Mergefunktion mal kommentieren? Und vermeiden, Variablen l1 oder l2 zu nennen? Das kann kein Mensch unangestrengt von 11 und 12 unterscheiden.
Die Aufgabenstellung verlangt, dass du die Elemente innerhalb deiner sortMergefunktion kopierst. Und das ist auch nicht ganz ohne Sinn.
Müsst ihr das mit new/delete machen? Könnt ihr nicht einfach vector nehmen? Falls new/delete: Benutz hinterher auf jeden Fall einen Speicherdebugger, ob auch alles sauber freigegeben wurde.
-
Habe das nun überarbeitet:
void sortMerge(int n, int *a){ void merge(int *a1, int laenge1, int *a2, int laenge2); if (n>1) { // Wenn Array mehr als 1 Element enthält sortMerge(n/2, a); sortMerge((n+1)/2, a + n/2); merge(a, n/2, a + n/2, (n+1)/2); } } void merge(int *b, int laenge1, int *c, int laenge2){ int pos1 = 0, pos2 = 0; //Positionen im Array int *temparray = new int[laenge1+laenge2]; for (int i = 0; i < laenge1 + laenge2; i++){ if (pos1 == laenge1) //erster Array zuende temparray[i] = c[pos2++]; else if (pos2 == laenge2) //zweiter Array zuende temparray[i] = b[pos1++]; else if (b[pos1] > c[pos2]) temparray[i] = c[pos2++]; else temparray[i] = b[pos1++]; } //Rückkopieren in Array for (int i = 0; i < laenge1; i++) b[i] = temparray[i]; for (int i = laenge1; i < laenge1 + laenge2; i++) c[i-laenge1] = temparray[i]; }Die Aufgabenstellung verlangt, dass du die Elemente innerhalb deiner sortMergefunktion kopierst. Und das ist auch nicht ganz ohne Sinn.
Meinst du, dass die Funktion "merge" direkt in "sortMerge" integriert sein soll?
Müsst ihr das mit new/delete machen? Könnt ihr nicht einfach vector nehmen? Falls new/delete: Benutz hinterher auf jeden Fall einen Speicherdebugger, ob auch alles sauber freigegeben wurde.
Ja, wir sollen das mit new/delete machen.
Was sind Speicherdebugger?
-
Thunderstick schrieb:
Habe das nun überarbeitet:
void sortMerge(int n, int *a){ void merge(int *a1, int laenge1, int *a2, int laenge2); if (n>1) { // Wenn Array mehr als 1 Element enthält sortMerge(n/2, a); sortMerge((n+1)/2, a + n/2); merge(a, n/2, a + n/2, (n+1)/2); } } void merge(int *b, int laenge1, int *c, int laenge2){ int pos1 = 0, pos2 = 0; //Positionen im Array int *temparray = new int[laenge1+laenge2]; for (int i = 0; i < laenge1 + laenge2; i++){ if (pos1 == laenge1) //erster Array zuende temparray[i] = c[pos2++]; else if (pos2 == laenge2) //zweiter Array zuende temparray[i] = b[pos1++]; else if (b[pos1] > c[pos2]) temparray[i] = c[pos2++]; else temparray[i] = b[pos1++]; } //Rückkopieren in Array for (int i = 0; i < laenge1; i++) b[i] = temparray[i]; for (int i = laenge1; i < laenge1 + laenge2; i++) c[i-laenge1] = temparray[i]; }Ok, das sieht doch recht in Ordnung aus. Gibt es noch Gründe zur Klage? Funktioniert es?
Die Aufgabenstellung verlangt, dass du die Elemente innerhalb deiner sortMergefunktion kopierst. Und das ist auch nicht ganz ohne Sinn.
Meinst du, dass die Funktion "merge" direkt in "sortMerge" integriert sein soll?
Nein, das ist schon ok so. Es hält sich zwar nicht 100% an die Aufgabenstellung, aber das ist Geschmackssache.
Müsst ihr das mit new/delete machen? Könnt ihr nicht einfach vector nehmen? Falls new/delete: Benutz hinterher auf jeden Fall einen Speicherdebugger, ob auch alles sauber freigegeben wurde.
Ja, wir sollen das mit new/delete machen.
Was sind Speicherdebugger?Ein Programm welches dir sagt, ob du bei new/delete-Orgien etwas falsch gemacht hast. So wie du es hast, denn dein temparray wird nirgends mehr freigegeben. Ein Beispiel dafür wäre valgrind.
-
Habe das Ganze jetzt etwas anders gestaltet.
Ich denke, dass das nun eher an der Aufgabenstellung liegt?void sortMerge(int n, int *a){ void merge(int *a,int p,int *b,int q, int *c,int n); if (n>1) { // wenn Array mehr als 1 Element enthält int *b = new int[n/2]; int *c = new int[(n + 1)/2]; int i; for(i=0; i < n/2; i++) { // Erste Hälfte in b kopieren b[i] = a[i]; } for(i=n/2; i < n; i++) { // Zweite Hälfte in c kopieren c[i - n/2] = a[i]; } // Arrays einzeln rekursiv sortieren sortMerge(n/2, b); sortMerge(n-n/2, c); // Arrays b und c zusammenfügen merge(b,n/2,c,n-n/2,a,n); // Arrays b und c wieder löschen delete b; delete c; } } void merge(int *b,int p,int *c,int q, int *a,int n) { int i=0,j=0,k=0; while(i<p && j<q) // solange Arrays b und c noch Elemente enthalten { if(b[i]<=c[j]) { // wenn i-tes Element von b größer-gleich i-tes Element von c a[k]=b[i]; i++; } else { a[k]=c[j]; j++; } k++; } if(i==p) { // restlichen Elemente von c in a kopieren while(j<q) { a[k]=c[j]; j++; k++; } } else { // restlichen Elemente von b in a kopieren while(i<p) { a[k]=b[i]; i++; k++; } } }Vielen Dank schon mal.
