Pourquoi mon tri par fusion ne fonctionne pas?

Question

Il compile très bien, mais quand il court, il ajoute un nombre élevé aléatoires à la liste, ainsi que les doublons des nombres existants. J'ai eu un couple de personnes regarder par-dessus cela, et aucun d'eux ne peut comprendre.

void mergeSort(int list[], int length) { 
    recMergeSort(list, 0, length - 1); 
} 

void recMergeSort(int list[], int first, int last) { 

    if (first < last) { 
     int mid = (first + last)/2; 
     recMergeSort(list, first, mid); 
     recMergeSort(list, mid + 1, last); 
     merge(list, first, last, mid); 
    } 
} 

void merge(int list[], int first, int last, int mid) { 

    int arraySize = last - first + 1; 
    int* tempList = new int[arraySize]; 
    int beginPart1 = first; 
    int endPart1 = mid; 
    int beginPart2 = mid + 1; 
    int endPart2 = last; 


    int index = beginPart1; 


    while (beginPart1 <= endPart1 && beginPart2 <= endPart2) { 
     if (list[beginPart1] < list[beginPart2]) { 
      tempList[index] = list[beginPart1]; 
      beginPart1++; 
     } 
     else { 
      tempList[index] = list[beginPart2]; 
      beginPart2++; 
     } 
     index++; 
    } 

    while (beginPart1 <= endPart1) { 
     tempList[index] = list[beginPart1]; 
     index++; 
     beginPart1++; 
    } 

    while (beginPart2 <= endPart2) { 
     tempList[index] = list[beginPart2]; 
     index++; 
     beginPart2++; 
    } 


    for (int i = first; i <= last; i++) { 
     list[i] = tempList[i - first]; 
    } 

    delete[] tempList; 
} 

Answer 1

En fusion de fonction(), vous ne calcule pas correctement la variable index:

En supposant begin = 10, mid = 14, end = 19 (pour une taille de tableau total de 0 .. 19, et vous êtes recMergeSort() dans la moitié supérieure), votre index = 10, mais le tableau tempList est indexé 0..9 (car arraySize = last - first + 1 == 10).

Vous êtes débordant votre tableau tempList, et quand vous « fusionner », vous obtenez la corruption de données.

Fixez votre variable index à 0 (plutôt qu'à beginPart1).

Answer 2

Si je lance cela en C# je reçois un IndexOutOfRangeException sur la ligne suivante:

    tempList[index] = list[beginPart1]; 

Je pense que si vous le tracer à travers vous utilisez probablement l'extrémité d'un tampon quelque part où les nombres aléatoires.

Answer 3

Je pense que problème ici est:

int index = beginPart1; 

Il devrait être

int index = 0;