Merge Art Fehler in C

Question

Ich will merge implementieren Art, obwohl sie nicht von der Klasse erforderlich ist, ich nehme.

Unten ist mein Code und ich habe einige printf Funktionen links enthalten den Fehler zu demonstrieren.

Das Programm scheint zu funktionieren, aber wie ich meine paar letzte verschmilzt in der Rekursion bekommen beginnt es außerhalb der Parameter des Arrays zu gehen und beginnt zu vergleichen Müll Werte. Es funktioniert, weil diese Werte positiv sind, aber wenn einer negativ ist, würde er den Wert in meinem Array speichern.

Ich habe versucht, den Fehler zu finden und das Beste, was ich sehen kann ihn mit den relationalen Operatoren zu tun hat, aber ich kann das Update nicht finden.

Jeder Punkt in der richtigen Richtung wäre sehr dankbar.

#include <stdio.h> 

#define SIZE 21 

int temp_array[SIZE] = {0}; 

void sort(int array[], int start, int end); 
void merge(int array[], int start_1, int end_1, int start_2, int end_2); 

int main() 
{ 

    int array[SIZE] = {10, 1, 8, 3, 6, 5, 4, 7, 2, 9, 0, 100, 91, 98, 93, 96, 95, 94, 97, 92, 99}; 

    sort(array, 0, SIZE-1); 

    for(int i = 0; i < SIZE; i++) 
    { 
     printf(" %i ", array[i]); 
    } 

} 


void sort(int array[], int start, int end) 
{ 
    if (end > start) 
    { 
     int middle = (start + end)/2; 

     // sort left half 
     printf("sorting left half\n"); 
     sort(array, start, middle); 

     // sort right half 
     printf("sorting right half\n"); 
     sort(array, middle + 1, end); 

     // merge the two halves 
     printf("####MERGING#####\n"); 
     merge(array, start, middle, middle + 1, end); 

    } 
} 

void merge(int array[], int start_1, int end_1, int start_2, int end_2) 
{ 
    int counter = 0; 
    int s1 = start_1; 

    while(start_1<=end_1 && start_2<=end_2) 
    { 
     printf(" %i %i and %i %i\n", start_1, end_1, start_2, end_2); 

     if(array[start_1] < array[start_2]) 
     { 
      printf("selecting %i over %i\n", array[start_1], array[start_2]); 
      temp_array[counter++] = array[start_1++]; 
     } 

     else 
     { 
      temp_array[counter++] = array[start_2++]; 
      printf("selecting %i over %i\n", array[start_2], array[start_1]); 
     } 
    } 

    while (start_1 <= end_1) 
    { 
     temp_array[counter++] = array[start_1++]; 
     printf("Dumping Left Half: placing %i in position %i\n", array[start_1], counter); 
    } 

    while (start_2 <= end_2) 
    { 
     temp_array[counter++] = array[start_2++]; 
     printf(" Dumping Right Half: placing %i in position %i\n", array[start_2], counter); 
    } 

    for(int i = s1, j = 0; i <= end_2; j++, i++) 
    { 
     printf("Placing %i in position %i\n", temp_array[j], i); 
     array[i] = temp_array[j]; 
    } 

    return; 
} 

Answer 1

Eine Sache, die ich verdächtig aussieht, ist dies innerhalb dieser else in Ihrem merge Code:

temp_array[counter++] = array[start_2++]; 
printf("selecting %i over %i\n", array[start_2 /* HERE */], array[start_1]); 

Unter der Annahme start_2 == end_2 hält, bevor die oben ausgeführt wird, dann wird die printf aus dem Index end_2 + 1 gelesen wird, die wird in dem äußersten rekursiven Aufruf von sort und damit undefiniertem Verhalten außerhalb der Grenzen sein (was zum Drucken von Müll führen könnte).