?
cliffhanger schrieb:
#include <iostream>
using namespace std;
void mergesort(int a[], int l, int r)
{
int i, j, k, m;
Definire Deine Variablen dann, wenn Du sie brauchst. Nicht vorher ohne Grund.
cliffhanger schrieb:
if(r > 1)
{
int b[r];
Schalte mal die Warnungen Deines Compilers ein. Wenn Dein Compiler dies hier frisst, liegt das an einer Erweiterung. Das ist kein C++. Er sollte Dich warnen. Bei so einem Array muss die Größe eine Compile-Zeit-Konstante sein. Hier ist r aber keine solche Konstante.
cliffhanger schrieb:
m = (r+l)/2;
mergesort(a, l, m);
mergesort(a, m+1, r);
Warum nicht mergesort(a,m,r); ? Offensichtlich ist die Linke Grenze bei dir inklusive und die rechte exklusive. Sonst würdest Du ein 10-elementiges Array nicht mit mergesort(dings,0,10); aufrufen.
cliffhanger schrieb:
for (i= m+1; i>l; i--) b[i-1] = a[i-1];
for (j = m; j < r; j++) b[r+m-j] = a[j+1];
for(k=l; k<= r; k++)
a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
Hier ist mit Sicherheit der Wurm drin. Greifst Du hier nicht eventuell in der letzten Zeile auf Elemente zu, die es gar nicht gibt, weil die Indizes i bzw j eventuell schon "hinter das Ende zeigen"?
Ich schließe mich drakon an. Mach nicht alles in einer Funktion. Das mit dem temporären Array muss man auch nur einmal machen:
/// [left,centr) und [centr,end) sind schon sortiert.
/// Diese Funktion kombiniert beite Sequenzen und legt sie bei "wohin" ab.
void internal_merge(int const* left, int const* centr, int const* end, int* wohin)
{
int const* p1 = left;
int const* p2 = centr;
while (p1!=centr && p2!=end) {
...
}
while (p1!=centr)
...
while (p2!=end)
...
}
void internal_mergesort(int len, int* arr, int* tmp)
{
if (len<2) return;
int const l1 = len/2;
int const l2 = len - l1;
internal_mergesort(l1,arr ,tmp );
internal_mergesort(l2,arr+l1,tmp+l1);
internal_merge(arr,arr+l1,arr+len, /* --> */ tmp);
std::copy(tmp,tmp+len,arr);
}
void mergesort(int len, int arr[])
{
std::vector<int> tmp (len);
internal_mergesort(len,arr,&tmp[0]);
}
kk
