Rekursives Merge-Sort In C++

Ich versuche code ein merge-sort in c++, sondern bauen es gibt mir eine Warnung, dass es rekursiv ist, und ausgeführt, es gibt ein stack-überlauf. Ich verstehe nicht, wo ich falsch mache.

void mergesort(int thelist[]) {
  if (sizeof(thelist) <= 1)
    return;

  int middle = (sizeof(thelist) / 2);
  for (i = 0; i <= sizeof(thelist); i++){
    if (i < middle)
      lft[i] = thelist[i];
    else if (i >= middle)
      rght[i-middle] = thelist[i];
  }
  mergesort(lft);
  mergesort(rght);
  merge(lft, lft + 10, rght, rght + 10, sortedlist);
}

sizeof() bedeutet nicht, was Sie denken, es bedeutet.
Warum gibt es eine 10 begraben in Ihrem code. Sie müssen übergeben Sie die Sequenz-Länge. sizeof(theist) ist nicht das tun, was Sie denken, es ist. Ihre mergsesort Erklärung sollte void mergesort(int thelist[], size_t len) und sizeof sollte nirgendwo in dieser Funktion. Weiters kann ich mir nur vorstellen, Sie sind mit globals für lft und rght, und ich kann Ihnen sagen, jetzt es ist nicht zu tun, was Sie denken, es wird.
Sie haben eine ständig endende rekursive Schleife als if (sizeof(thelist) <= 1) ist immer false, da sizeof(thelist) ist die Größe eines Zeigers. Du musst ein zusätzliches argument - size_t size sagt die Größe der thelist array.
Wie sind Sie den code testen? Was ist der stack-trace? Wo ist Zusammenführen? Je mehr Informationen Sie liefern, desto besser können wir werden, Ihnen zu helfen.

InformationsquelleAutor William | 2014-01-03

c++merge recursion sorting

1
1. Wenn Sie wollen, um die Handhabung der verschiedenen Teile der int [] durch den Aufruf der gleichen Funktion, zu definieren versuchen, Ihre Funktion als
```
void mergesort(int thelist[], int start, int end)
```
2. Bezüglich der sizeof(thelist) Teil, wenn Sie wollen, um die Größe eines int []. Sie benötigen
```
sizeof(thelist)
```
  statt
```
sizeof(thelist)/sizeof(int)
```
  Beispiel:
```
int a[] = {1, 2, 3, 4, 5};
int n = sizeof(a)/sizeof(int); //n=5 now
```
PS: Sie müssen auch zweimal überlegen, auf Ihre code-Logik-und umschreiben. Sie die main-Funktion sollte wie folgt aussieht:
```
void MergeSort(int data[], int start, int end)
{
    if (start < end)
    {
        int middle = (start+end)/2;

        //sort for first part
        MergeSort(data, start, middle);

        //sort for second part
        MergeSort(data, middle+1, end);

        //merge both parts together
        Merge(data, start, middle, end);
    }
}
```
- leider, in den Kontext der Funktion, der sizeof thelist/sizeof int wird nicht funktionieren. (in C, aber ich bin mir fast sicher in C++ auch)
- Es sollte in C++. Siehe das Beispiel (Hinzugefügt).
- das Beispiel funktioniert in C ebenso, aber das problem ist, dass nicht klar ist, ob Sie was auf die Verwendung in der angerufene oder der Anrufer; der angerufene, wird es nicht funktionieren. — und der Anrufer wird funktionieren, wenn er erklärt hat, den array, wie Sie es Tat.
- ist nur zu klären, wie Sie nach rechts verwenden sizeof() um die Größe. Sie haben Recht damit, dass er/Sie nicht nur diesen in den code, kombiniert mit #2 statt.
- Also, es ist nicht klar, da Sie vorschlagen, zu ersetzen sizeof mit sizeof/sizeof, und mir scheint es, Sie sind darauf hindeutet, es zu tun in der Funktion.
- Aktualisiert, um deutlich zu machen-er. Danke.
- Danke, aber mehr Informationen wären toll. Die "merge" - Funktion anscheinend braucht 5 Argumente, die nicht übereinstimmen mit deins, und ich denke, dass 'start' und 'Ende' sollen die ersten und letzten Elemente in das array, aber ich bin mir nicht sicher.
- Ja, ich habe nicht die endgültigen Merge() zum Zusammenführen von zwei sortierten arrays zusammen hier. Sie sollten in der Lage sein zu liefern.
InformationsquelleAutor herohuyongtao

#include <iostream>

using namespace std;

void merge(int *, int *, int, int, int);
void mergesort(int *a, int *b, int low, int high)
{
    int pivot;
    if (low < high)
    {
        pivot = (low + high)/2;
        mergesort(a, b, low, pivot);
        mergesort(a, b, pivot + 1, high);
        merge(a, b, low, pivot, high);
    }
}
void merge(int *a, int *b, int low, int pivot, int high)
{
    int h, i, j, k;
    h = low;
    i = low;
    j = pivot + 1;

    while ((h <= pivot) && (j <= high)) //Traverse both halves of the array
    {
        if (a[h] <= a[j]) //if an element of left half is less than element of right half
        {
            b[i] = a[h]; //store element of left half in the temporary array
            h++; //shift the index of the array from which the element was copied to temporary 
        }
        else //otherwise store the element of the right half in the temporary array
        {
            b[i] = a[j];
            j++; //shift the index of the array from which the element was copied to temporary 
        }
        i++;
    }
    if (h > pivot) //If traversal of left half is done, 
                   //copy remaining elements from right half to temporary
    {
        for (k = j; k <= high; k++)
        {
            b[i] = a[k];
            i++;
        }
    }
    else //otherwise copy remaining elements from left half to temporary
    {
        for (k = h; k <= pivot; k++)
        {
            b[i] = a[k];
            i++;
        }
    }
    for (k = low; k <= high; k++) a[k] = b[k]; //recopy the values from temporary to original array.
}

int main()
{
    int a[] = {12, 10, 43, 23, -78, 45, 123, 56, 98, 41, 90, 24};
    int num;

    num = sizeof(a)/sizeof(int);

    int b[num]; //temporary array to be used for merging

    mergesort(a, b, 0, num-1);

    for (int i = 0; i < num; i++)
        cout << a[i] << " ";
    cout << endl;
}

Sollten Sie einen text hinzufügen, die erklären, was dein code ist und warum dieser die Frage beantwortet.

InformationsquelleAutor Sumit Kandoi

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void print_arr_data(std::vector<int>& arr, int start, int end) {
    cout << "start: " << start << " end: " << end << endl;
    int len = abs(end - start) + 1;
    for(auto it = arr.begin() + start; it != arr.begin() + start + len; ++it) {
        cout << *it << ",";
    }
    cout << endl;
}

void merge(std::vector<int>& arr, int start, int end) {
    int len = abs(start - end);
    std::sort(arr.begin() + start, arr.begin() + start + len);
}

void merge_sort(std::vector<int>& arr, int start, int end) {
    //check if the array is not a unit array, then dont divide anymore
    print_arr_data(arr, start, end);

    if (start < end) {
        int mid = (start + end)/2;

        merge_sort(arr, start, mid);
        merge_sort(arr, mid+1, end);
        merge(arr, start, end);
    }
}

int main() {
    std::vector<int> data = {4,1,2,3,7,8,5,6,9};
    merge_sort(data, 0, data.size()-1);

    cout << "*******" << endl;
    for (int i : data) {
        cout << i << endl;
    }
    cout << "*******";

    return 0;
}

InformationsquelleAutor Pabitra Padhy

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.