Mergesort Problem

Hallo,
ich stecke in einem Problem mit Mergesort, vor allem deswegen, weil ich mir Rekursionen noch immer nicht vorstellen kann (da verknotet sich mein Hirn )

Hier einmal der Quellcode:

#include <iostream>
using namespace std;

void mergesort(int a[], int l, int r)
{
    int i, j, k, m;

    if(r > 1)
    {
        int b[r];
        m = (r+l)/2;
        mergesort(a, l, m);
        mergesort(a, m+1, r);
        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--];
    }
    else
    return;
}

int main()
{
    int array[10]={5, 6, 1, 9, 3, 2, 7, 4, 8, 10};
    int n=10;
    mergesort(array,0,n);

    for (int i=1; i<n; ++i)
       cout << array[i];

     return 0;
}

Das Programm compiliert, nur dann gibt es ein Segmentation Fault. Meine Frage: Wie kann ich mir die Ausführung des Codes vorstellen und was läuft schief?

Danke!

drakon

Am besten du teilst dein Problem mal auf. Probier zuerst eine Funktion merge zu schreiben, welche dir 2 Arrays (respektive 2 Teilarrays) merged.

Dann kannst du das testen und schauen, ob das überhaupt richtig gemacht wird (ich vermute, dass der Fehler da liegt). Und das sortieren besteht dann nur noch aus dem aufteilen und mergen lassen.

Der Debugger kann dir in solchen Fällen auch recht gut helfen.

Die Idee hinter Mergesort ist, dass du einfach sagst, dass ein Array sortiert ist, wenn du 2 (sortierte) Teilarrays hast und diese dann zusammenfügst (merge). Nun machst du das so oft, bis du sicher bist, dass ein Array sortiert ist und das ist es, wenn du nur noch eine Zahl hast. Dann werden da auf der untersten Stufe 2 vorsortierte Zahlen (2 Zahlen) gemerged und dann 2x2 usw. bist das ganze Array sortiert ist. Mach das mal am besten von Hand, dann siehst du recht gut, wie das geht.

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