Проблемы с сортировкой слияния с указателями в c

Question

Я пытаюсь написать программу сортировки слияния с указателями, и он близок к хорошему функционированию, но есть проблема, что на выходе есть некоторые «0», а не некоторые чисел отсортированного массива.

Для тестирования кода вам необходимо написать txt-файл prova.txt, в котором есть массив, один номер для строки. Например:

prova.txt:

4 
7 
2 
9 
1 
45 
87 

При выполнении кода, я ожидаю, что выход

0: 1 
1: 2 
2: 4 
3: 7 
4: 9 
5: 45 
6: 87 

, но я получаю

0: 1 
1: 0 
2: 0 
3: 0 
4: 0 
5: 0 
6: 2 

Кроме того, есть ли какие-либо советы что вы можете дать мне для улучшения моего кода?

#include <stdio.h> 

int *merge(int left[], int right[], int n){ 
     int *ordinato, i=0, j=0; 
     ordinato = malloc(sizeof(int)*n); 
     while(i+j < n){ 
      if(left[i] < right[j]){ 
       *(ordinato+i+j) = left[i]; 
       i++; 
      }else{ 
       *(ordinato+i+j) = right[j]; 
       j++; 
      } 
     } 
     return ordinato;  
} 

int *mergeSort(int *daOrd, int n){ 
     int k = 0, *left, *right, *ordinato; 
     ordinato = malloc(sizeof(int)*n); 
     left = malloc(sizeof(int)*(n/2)); 
     right = malloc(sizeof(int)*(n-(n/2))); 
     if (n<2){ 
     ordinato = daOrd;  
     }else{ 
     for(k=0; k<n/2; k++) 
      *(left + k) = *(daOrd + k); 
     for(k=n/2; k<n; k++) 
      *(right + k -(n/2)) = *(daOrd + k); 

     left = mergeSort(left, n/2); 
     right = mergeSort(right, n-(n/2)); 
     ordinato = merge(left, right, n); 
     }  
     return ordinato; 
} 

main(){ 
    FILE *input; 
    input = fopen("prova.txt", "r"); 
    if(!input) printf("Errore"); 

    int tot = 100000;//is the maximum n 

    int *array; 
    array = malloc(sizeof(int)*tot); 
    int indice = 0; 
    while(fscanf(input,"%d", (array + indice)) != EOF) indice++; 

    int *ord = mergeSort(array, indice); 

    int k; 
    for(k=0; k<indice; k++) printf("%d: %d \n",k, *(ord+k)); 


    getch(); 
    fclose(input);  
} 

Answer 1

Прежде всего, ваша программа только компилирует/ссылки, когда вы игнорировать ошибки. Добавьте #include <stdlib.h> для malloc и удалите вызов getch, который не нужен в этом примере. Кроме того, ваша функция main равна 1. неявно возвращение int и 2. отсутствие возврата.

Ваша программа не работает на шаге слияния - вы не считаете, что происходит, когда один из массивов заканчивается перед другим. Текущая прогама просто продолжает читать и захватывает все, что находится за массивом left или right, который чаще всего равен нулю.

Что вы хотите, чтобы сравнить только тогда, когда ни влево или вправо истощается, а затем просто добавить остальные значения, как это:

#include <stdlib.h> 
#include <stdio.h> 

void merge(const int* left, const int* right, int* res, int n) { 
    int i=0, j=0; 
    while ((i < n/2) && (j < n - (n/2))) { 
     if (left[i] < right[j]) { 
      res[i+j] = left[i]; 
      i++; 
     } else { 
      res[i+j] = right[j]; 
      j++; 
     } 
    } 
    while (i < n/2) { 
     res[i+j] = left[i]; 
     i++; 
    } 
    while (j < n-(n/2)) { 
     res[i+j] = right[j]; 
     j++; 
    } 

    return res; 
} 

void _mergeSort(int* values, int* aside, int n) { 
    if (n < 2) { 
     return; 
    } 
    _mergeSort(values, aside, n/2); 
    _mergeSort(values+n/2, aside+n/2, n-(n/2)); 
    merge(values, values + n/2, aside, n); 
    memcpy(values, aside, n * sizeof(int)); 
} 

void mergeSort(int* values, int n) { 
    int* aside = malloc(sizeof(int) * n); 
    _mergeSort(values, aside, n); 
    free(aside); 
} 

int main() { 
    FILE *input; 
    input = fopen("prova.txt", "r"); 
    if (!input) { 
     fprintf(stderr, "Could not open file"); 
     return 1; 
    } 

    int maximum_n = 100000; 
    int *array = malloc(sizeof(int)*maximum_n); 
    int count; 
    for (count = 0;count < maximum_n;count++) { 
     if (fscanf(input, "%d", (array + count)) == EOF) { 
      break; 
     } 
    } 
    mergeSort(array, count); 

    for(int k=0; k < count; k++) { 
     printf("%d: %d \n", k, array[k]); 
    } 
    return 0; 
} 

Обратите внимание, что есть только один malloc вызов внутри слиянием Теперь.

Answer 2

Рекомендации относительно оптимизации используемой памяти:
1. Если вы хотите выделить память, на каждом шагу (хотя это не обязательно) убедитесь, что вы бесплатно всю память используется, когда временные буферы больше не необходимо.
2. Нет необходимости создавать буферы на каждом шагу. Вы можете выделить буфер в начале и использовать указатели внутри этого массива на каждом шаге алгоритма.

И проблема связана с функцией слияния. Когда вы достигли конца одного из ваших массивов (справа или слева), вы указывали на память, которую вы не выделили. Там он нашел значение 0, которое всегда было меньше значений в оставшемся массиве. Таким образом, вы должны прекратить слияние, когда один из ваших буферов полностью копируется в результате, а затем копирует то, что осталось от другого.

Вы должны изменить его к этому:

int *merge(int left[], int right[], int n){ 
    int *ordinato, i=0, j=0, k; 
    ordinato = malloc(sizeof(int)*n); 
    while((i<n/2) && (j<n-n/2)){ 
     if(left[i] < right[j]){ 
      *(ordinato+i+j) = left[i]; 
      i++; 
     }else{ 
      *(ordinato+i+j) = right[j]; 
      j++; 
     } 
    } 
    while(i!=n/2){ 
     *(ordinato+i+j) = left[i]; 
     i++; 
    } 
    while(j!=n-n/2){ 
     *(ordinato+i+j) = right[j]; 
     j++; 
    } 
    return ordinato;  
}