Merge Sort-Algorithmus in C++

Question

Ich versuche, ein C++ - Programm zu schreiben, das ein Benutzereingabearray mit dem Merge-Algorithmus sortiert.

Hier ist die Split-Funktion:

void split(int numbers[], int size) { 
    if (size == 1) 
     return; 

    int mid = size/2; 
    int firstPartSize = mid; 
    int secondPartSize = size - mid; 

    int *firstArray; 
    firstArray = new int[firstPartSize]; 

    int *secondArray; 
    secondArray = new int[secondPartSize]; 

    for (int i = 0; i < size; i++) { 
     if (i < mid) 
      firstArray[i] = numbers[i]; 
     else 
      secondArray[i - mid] = numbers[i]; 
    } 

    split(firstArray, firstPartSize); 
    split(secondArray, secondPartSize); 
    merge(numbers, firstArray, firstPartSize, secondArray, secondPartSize); 
} 

Hier ist die Vereinigungsfunktion:

void merge(int outputArray[], int firstArray[], int n1, int secondArray[], int n2) { 
    int k = 0; 
    int i = 0; 
    int j = 0; 
    while (i < n1 && j < n2) { 
     if (firstArray[i] < secondArray[j]) 
      outputArray[k++] = firstArray[i++]; 
     else 
      outputArray[k++] = secondArray[j++]; 
    } 

    while (i < n1) 
     outputArray[k++] = firstArray[i++]; 
    while (j < n2) 
     outputArray[k++] = secondArray[j++]; 

    for (int c = 0; c < n1+n2; c++) 
    { 
     cout << outputArray[c] << " "; 
    } 
} 

Wenn ich versuche, ein Array einfügen, hier ist was ich

Enter the size of the array you want to sort: 
3 
Enter the elements of the array: 
4 
7 
1 
1 7 1 4 7 Press any key to continue 

bekommen Was bin ich hier fehlt?

Answer 1

Der Code ist insgesamt mit einem einfachen Fehler korrekt. Sie drucken die Ausgabe in einem der rekursiven Schritte und erhalten daher die Zwischenergebnisse mit der Antwort gemischt.

Entfernen der cout in der merge Funktion und es heraus zu einer main Funktion bewegt den Trick:

void merge(int outputArray[], int firstArray[], int n1, int secondArray[], int n2) { 
    int k = 0; 
    int i = 0; 
    int j = 0; 
    while (i < n1 && j < n2) { 
     if (firstArray[i] < secondArray[j]) 
      outputArray[k++] = firstArray[i++]; 
     else 
      outputArray[k++] = secondArray[j++]; 
    } 

    while (i < n1) 
     outputArray[k++] = firstArray[i++]; 
    while (j < n2) 
     outputArray[k++] = secondArray[j++]; 

} 

int main(int argc, char *argv[]) { 

    int a[] = {1, 4, 7}; 
    int n = sizeof(a)/sizeof(int); 
    split(a, n); 

    cout << "The array is:\n"; 
    for (int i = 0; i < n; i++) { 
     cout << a[i] << " "; 
    } 
    cout << endl; 

    return 0; 
} 

Ausgang:

The array is: 
1 4 7