Merge Sort

Hashimura

Grünschnabel
Hallo Leute,
Wir sollten für die Uni den Merge Sort Programmieren in C++ und dessen Laufzeit messen,
nun meine frage, wieso stürzt das Programm bei 260.000+ Feldern ab ?

Gruß Hashimura.
Hier mal den Code, vielleicht ist da iwas falsch.
C++:
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

void merge_sort(int [],int ,int );
void merge(int [],int,int ,int );

int main()
{
    int n = 0;
    for(int i = 0 ; i <= 20 ; i++){
    n += 20000;
    int a[n];

    for(int i = 1 ; i <= n ; i++){
        a[i] = rand();
    }
    int p=1,r=n;

    double start = clock();
    merge_sort(a,p,r);
    double end = clock();
    cout << i << ". " << n << " Felder  |  Zeit : " << (end - start) / CLOCKS_PER_SEC << " sekunden."<<"\n";
    }
}

void merge_sort(int a[],int p,int r)
    {
        int q;
        if(p<r)
        {
        q=(p+r)/2;
        merge_sort(a,p,q);
        merge_sort(a,q+1,r);
        merge(a,p,q,r);
        }
    }

 void merge(int a[],int p,int q,int r)
    {
        int n1=q-p+1;
        int n2=r-q;
        unsigned long long Max_Zahl = 18446744073709551;
        int L [n1 + 1] ;
        int R [n2 + 1] ;
        for(int i=1;i<=n1;i++)
        {
            L[i]=a[p+i-1];
        }
        for(int j=1;j<=n2;j++)
        {
            R[j]=a[q+j];
        }
        L[n1+1]= Max_Zahl;
        R[n2+1]= Max_Zahl;
        int i=1, j=1;
        for(int k=p;k<=r;k++)
        {
            if(L[i]<=R[j])
            {
                a[k]=L[i];
                i=i+1;
            }
            else
            {
                a[k]=R[j];
                j=j+1;
            }
        }
    }
[/code}
 

cwriter

Erfahrenes Mitglied
Hi
Wir sollten für die Uni den Merge Sort Programmieren in C++ und dessen Laufzeit messen
Warum nutzt du nicht Klassen, wenn du eh C++/STL nutzt? Momentan ist es C mit ein bisschen C++ dazwischen.
entscheide dich erst einmal, ob es C oder C++ werden soll.
So kann man es auch sagen :)

Zum Code selbst:
Dein rand() ist nutzlos so. Du hast die Werte nicht initialisiert (srand()), es wird also nicht wirklich zufällig sein. Da du C++ benutzen willst, gibt es extra dafür random (http://www.cplusplus.com/reference/random/), wodurch die Zufallszahlen richtig verteilt sind (die C-Art ist sehr fehleranfällig. Nicht, dass es wichtig wäre, da man rand() nicht für Security/Crypto verwenden darf).

C++:
for(int i = 0 ; i <= 20 ; i++){ //im Loop?
    n += 20000;
    int a[n]; //Neuer Array

    for(int i = 1 ; i <= n ; i++){
        a[i] = rand(); //noch ein Loop? Wofür denn das?
    }

C++:
double start = clock();
Ernsthaft? Dein Compiler muss dir ja die Warnungen richtiggehend ins Gesicht brüllen...

C++:
int a[]
unsigned long long Max_Zahl = 18446744073709551;
//...
int L [n1 + 1] ;
L[n1+1]= Max_Zahl;
Seufz.
Dein Code ist recht kreativ - so ziemlich mit allem.

nun meine frage, wieso stürzt das Programm bei 260.000+ ab ?
Mein Verdacht (ohne den ganzen Code geprüft zu haben): Kein Speicher mehr? Was sagt denn der Debugger? Stack Overflow? Rekursionen sind sehr teuer. Ansonsten brauchen wir mehr Informationen (und besseren Code).
Übrigens geht Mergesort in-place. Damit solltest du zumindest ein bisschen grössere Arrays sortieren können.

Oh und äh: Dein int a[] ist invalid, da du deine Arrays auf dem Stack erstellst. Innerhalb des Loop-Scopes. Nach dem Verlassen des Loops ist a[] invalid, und daher ist jeder Zugriff ein Herumspielen am Zünder namens "UB".
Nein, nein, nur schlecht eingerückt...

Gruss
cwriter
 
Zuletzt bearbeitet:

sheel

I love Asm
...und da es C++ sein soll, "int a[n];" durch std::vector ersetzen (und dann mit .data() ein C-Array bekommen) oder zumindest new/delete[] verwenden. Dein derzeitiger Code ist nämlich kein gültiges C++.
 

cwriter

Erfahrenes Mitglied
Dein derzeitiger Code ist nämlich kein gültiges C++.
Wie meinst du?
Die Stack-Arrays sind zwar hässlich (und wahrscheinlich zusammen mit der Rekursion der Grund, warum das Programm abschmiert), aber ungültiges C++ sehe ich nicht (bzw. vielleicht falsch :) ).
...und da es C++ sein soll, "int a[n];" durch std::vector ersetzen (und dann mit .data() ein C-Array bekommen)
Der operator[] sollte es eigentlich auch tun. Als Parameter gingen const references bzw. besser mit vektor als Member und die Parameter entfallen...
zumindest new/delete[] verwenden
Das wäre wahrscheinlich sogar am reinsten für eine Uniaufgabe :)

Gruss
cwriter

/EDIT:
@Hashimura:
Beim wiederholten Durchlesen des Codes komme ich schlicht auf einen Schluss: So hart das tönen mag, dir fehlen noch seeeeehr viele Basics (oder du machst sie nur hier falsch), um in der Lage zu sein, Mergesort zu implementieren.
Ich schlage dir folgenden Deal vor: Ich gehe den gesamten Code mit dir durch, wenn du eine C++ (klassenbasierte) Version beginnst. Ob mit std::vector, int* mit malloc oder int* mit new[] ist mir dabei egal.
Ich habe allerdings keine Lust, deinen momentanen Code durchzugehen; dieser ist schlicht zu fehlerzersetzt...
 
Zuletzt bearbeitet:

sheel

I love Asm
@cwriter
Dass die Arraygröße variabel sein kann (="variable length array"=VLA) ist in C99 erlaubt, und in manchen Compilern auch in C++ möglich (wenn auch leicht anders als die C99-Variante), aber nicht Teil von irgendeinem C++-Standard. Zwischen 11 und 14 gabs zwar ein Proposal, dass aber nicht angenommen wurde.

Der operator[] sollte es eigentlich auch tun
Wenn man die Funktionen auch ändern will, ja :)
 
Zuletzt bearbeitet:

cwriter

Erfahrenes Mitglied
aber nicht Teil von irgendeinem C++-Standard.
Oh, da sind die "Dragons of C++" mal wieder:confused:... VLAs machen ja eigentlich schon Sinn, wenn man bei kleinen 'n' bleibt (da sehr viel schneller als Heap). Wobei SO wieder mit "Es macht keinen Sinn, da man nur VLAs verwenden sollte, wenn man weiss, dass man weniger als z.B. 1000 Elemente haben will, und dann kann man auch gleich einen statischen 1000er-Array aufschreiben" ein bisschen herumblödelt (wenn man in 90% der Fälle nur 4 Elemente braucht, soll man nicht 1000 reservieren) :rolleyes:

Für Hashimuras Zwecke sind VLAs aber tatsächlich ungeeignet.

Aber back2topic:
Wenn man die Funktionen auch ändern will, ja :)
Du wirst mir doch durchaus zustimmen, wenn ich sage, dass ein Grossteil der Funktionen eh neu geschrieben werden muss, oder?

Gruss
cwriter