Hilfe mit Mergesort

Bashar

Cabooze schrieb:

Oh glaub mir für den Rekursionsteil hab ich noch länger gebraucht.

Das muss nur einmal klick machen, dann ist Rekursion das einfachste von der Welt, und man kann es einfach so runterschreiben. Was ist denn MergeSort eigentlich?

mergesort(A):
  if A hat nur ein Element (oder ist sogar leer):
     A ist schon sortiert
  else:
     zerteile A in der Mitte in A1 und A2
     mergesort(A1)   // MAGIE
     mergesort(A2)
     füge A1 und A2 zu A zusammen (Merge-Schritt)

Tu einfach so als hättest du die Funktion schon geschrieben. Mathematisch gesehen ist entscheidend, dass das Array, mit dem du den rekursiven Aufruf machst, kleiner ist als das ursprüngliche. So ist sichergestellt, dass das ganze sich irgendwann wieder entwirrt. Aber davon die Details immer im Blick zu haben ist überflüssig. Wenn man einmal ein Gefühl dafür hat, was es heißt, ein Problem zu verkleinern, schreibt sich Rekursion von selbst.

Cabooze

Naja mal schauen

Ich hab jetzt noch eine kleine Sache.
ALso so sieht das jetzt aus:

void merge(int A[],int lo, int mid, int hi){

    int*ptr=new int[lo+hi];

    for(int i=lo;i<=hi;i++){
        ptr[i]=A[i];  //Kopiere Array in Hilfsarray
    }
    int m=mid+1;
    int l=lo;
    int i=lo;
    while(l<=mid && m<=hi){

        if(ptr[l]<=ptr[m]){
            A[i]=ptr[l];
            l++;
        }
        else{
            A[i]=ptr[m];
            m++;
        }    
        i++;
    }

    while (l<=mid || m<=hi){ //reste in array einfügen
        if (l<=mid){
            A[i]=ptr[l];
            l++;
            i++;
        }
        if (m<=hi){
            A[i]=ptr[m];
            m++;
            i++;
        }
    }

    delete [] ptr;
}

void mergesort(int A[], int lo, int hi){
    int mid;

    if (lo < hi){             // Größe des Teilarrays ist größer 1
        mid = (lo + hi) / 2;            // Teile in der Mitte
        mergesort(A, lo, mid);             // Sortiere linken Teil
        mergesort(A, mid + 1, hi);             // Sortiere rechten Teil
        merge(A, lo, mid, hi);
    }

}

int main() {

    time_t vorher=time(NULL);

    const int n=100000;
    int A[n];
    int lo=0,hi=n-1;

    for (unsigned int i=0; i < n; i++)
        A[i] = rand();

    mergesort(A,lo,hi);

    //for(int i=0;i<n;i++)
        //cout << A[i] << " ";

    time_t nachher=time(NULL);

    cout << "Dauer: " << nachher-vorher << "sec" << endl;

    return 0;
}

Wir sollen das ganze Spiel nun mit einer Zeitmessung machen. Und zwar einmal mit 100.000 mit 200.000 Feldern usw bis 500.000 Felder.
Allerdings meldet er "run failed" wenn ich für die Feldgröße n zu viel eingebe. Woran liegt das? 10.000 schluckt er noch. 100.000 schon nicht mehr.

Cabooze

Ok das ist echt seltsam. Gebe ich für n 10 ein funktioniert es. bei 100 nicht. bei 13 nicht. Bei 15 nicht. Bei 10.000 funktioniert es wieder.

implement die standard lib eine kombination aus merge und quicksort?

e.g. wenn man koennte mit quicksort beginnen und wenn man merkt, quicksort endet in einer laufzeit von O(N^2) dann koennte man zu merge sort welchen um das sortieren un O(N) zu machen? leider verbraucht merge sort etwas mehr speicher als quicksort, speicherkomplexitaet: O(N)

HarteWare

Bei 10.000 funktioniert es wieder? GCC4.9 crashed (also das Programm, dass damit kompiliert wurde), VC++12 sagt

Debug Error:
HEAP CORRUPTION DETECTED: ...
CRT detected that the application wrote to memory after end of heap buffer.

In folgender Zeile:

delete[] ptr;

Undzwar nicht nur bei 10.000, sondern auch bei 10, 13, ... Das wird Zufall gewesen sein.

Cabooze schrieb:

void merge(int A[],int lo, int mid, int hi){
   
    int*ptr=new int[lo+hi];
   
    for(int i=lo;i<=hi;i++){
        ptr[i]=A[i];  //Kopiere Array in Hilfsarray
    }
    ...
}

Der Part ist "fragwürdig", wenn Du mal drüber nachdenkst...

Skym0sh0

goofyy schrieb:

implement die standard lib eine kombination aus merge und quicksort?

Das ist durch den Standard nicht sichergestellt. Soweit ich mal irgendwo gelesen habe ist std::sort im GCC als Quicksort mit gewissen Abänderungen eingebaut, so dass der bei einer degenerierten Sortieraktion in einen Heapsort verfällt. So wird die Laufzeit bei O(n*log n) gehalten.

goofyy schrieb:

e.g. wenn man koennte mit quicksort beginnen und wenn man merkt, quicksort endet in einer laufzeit von O(N^2) dann koennte man zu merge sort welchen um das sortieren un O(N) zu machen? leider verbraucht merge sort etwas mehr speicher als quicksort, speicherkomplexitaet: O(N)

Ist quatsch, erstens ist Mergesort auch "nur" O(n*log n) (wie Quicksort im Mittel) und zweitens kommt man wahrscheinlich gerade als Anfänger nicht gegen eine Compiler Implementierung von der Laufzeit her dran. Vor allem nicht wenn man bedenkt, was dort alles für Sicherheitsmechanismen eingebaut sind. Siehe auch z.B. Punkt 5 hier.

Cabooze

Furble Wurble schrieb:

Cabooze schrieb:

void merge(int A[],int lo, int mid, int hi){
   
    int*ptr=new int[lo+hi];
   
    for(int i=lo;i<=hi;i++){
        ptr[i]=A[i];  //Kopiere Array in Hilfsarray
    }
    ...
}

Der Part ist "fragwürdig", wenn Du mal drüber nachdenkst...

Ok also hab jetzt das hier korrigiert:

int*ptr=new int[mid+hi]

Cabooze schrieb:

Furble Wurble schrieb:
Cabooze schrieb:
void merge(int A[],int lo, int mid, int hi){
   
    int*ptr=new int[lo+hi];
   
    for(int i=lo;i<=hi;i++){
        ptr[i]=A[i];  //Kopiere Array in Hilfsarray
    }
    ...
}
Der Part ist "fragwürdig", wenn Du mal drüber nachdenkst...
Ok also hab jetzt das hier korrigiert:
int*ptr=new int[mid+hi]

Ich dachte eher daran, dass die Elemente von ptr die Indices [0...lo+hi) haben, und Du aber die Elemente [lo...hi] indizierst.
Zumindest wenn lo==0 greifst Du eins hinter dass Array. Später auch wieder.
Volkard macht das besser mit den halboffenen Intervallen. Er hat's Dir auch ans Herz gelegt.

Ob Deine Änderung jetzt besser ist: keine Ahnung. Kann mid==0 werden?

volkard

[hi+1] wäre es wohl. auch wenn dann die plätze von 0 bis lo-1 nicht verwendet werden. eigentlich würde [hi-lo+1] reichen, aber dann wirds zu schwer zu programmieren, weil die indizes im ptr-array anders als die in A wären.

bei den halboffenen intervallen wäre es entsprechend [hi] statt [hi+1]. aber [lo+hi] führt zu keinem absturz, weil lo>=0.

Th69

Genau das meinte ich mit meiner Anmerkung