Как я могу найти причину сбоя моего алгоритма сортировки слиянием при сортировке массива из 1 миллиона элементов? - PullRequest
Новая
       83

Как я могу найти причину сбоя моего алгоритма сортировки слиянием при сортировке массива из 1 миллиона элементов?

1 голос
/ 02 апреля 2019

Я студент из Франции и пытаюсь рассчитать время выполнения алгоритма сортировки слиянием для разных размеров массива.Я также хочу записать другое время выполнения в файле .csv.Но когда моя программа пытается отсортировать массив с 1 миллионом элементов, процесс возвращает -1073741571 (0xC00000FD) в Code :: Blocks.Поэтому, если бы вы могли указать мне, как найти решение, я был бы очень признателен!

Вот мой код: 

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

void genTab(int *tab, int n) {
    int i;
    for (i = 0; i < n; i++) {
        tab[i] = rand() % 100;  
    }
}

void fusion(int *tab, int deb, int mid, int fin) {
    int i = deb;
    int j = mid + 1;
    int k = deb;
    int temp[fin + 1];
    while ((i <= mid) && (j <= fin)) {
        if (tab[i] <= tab[j]) {
            temp[k] = tab[i];
            i++;
        } else {
            temp[k] = tab[j];
            j++;
        }
        k++;
    }
    while (i <= mid) {
        temp[k] = tab[i];
        i++;
        k++;
    }
    while (j <= fin) {
       temp[k] = tab[j];
       k++;
       j++;
    }

    for (i = deb; i <= fin; i++) {
        tab[i] = temp[i];
    }
}

void triFusion(int *tab, int i, int j) {
    if (i < j) {
        triFusion(tab, i, (int)((i + j) / 2));
        triFusion(tab, (int)((i + j) / 2 + 1), j);
        fusion(tab, i, (int)((i + j) / 2), j);
    }
}

void reset(int *tab1, int *tab2, int n) {
    for (int i = 0; i < n; i++) {       
        tab2[i] = tab1[i];
    }
}

int main() {
    srand(time(NULL));
    clock_t start, end;  

    int nbrTest[15] = {
        1000, 5000, 10000, 50000, 80000, 100000, 120000, 140000,
        150000, 180000, 200000, 250000, 300000, 450000, 1000000
    }; 
    FILE *fp;

    char *tpsExecution = "exeTime.csv";

    fp = fopen(tpsExecution, "w");

    fprintf(fp, "Array Size; Merge Time"); 

    for (int i = 0; i < 15; i++) {     
        int n = nbrTest[i];
        printf("Calculating time for an array of %d \n", n);
        int *tab = malloc(sizeof(int) * n);
        genTab(tab, n);      

        int *copie = malloc(sizeof(int) * n);
        reset(tab, copie, n);

        start = clock();
        triFusion(tab, 0, n - 1);
        end = clock();
        float tpsFusion = (float)(end - start) / CLOCKS_PER_SEC;

        reset(tab, copie, n);

        printf("writing in the file\n");
        fprintf(fp, "\n%d;%f", n, tpsFusion);    
        free(tab);
        free(copie);
    }
    fclose(fp);

    return 0;
}

Ответы [ 3 ]

2 голосов
/ 02 апреля 2019

int temp[fin+1]; может превышать ограничение пространства для стека.Вы должны выделить его с помощью malloc и освободить его с помощью free.

. Если вы хотите исключить malloc и free из временного кода, выделение может быть выполнено вне временного кода.и передан в качестве рабочего пространства.

1 голос
/ 03 апреля 2019

fusion () всегда выделяет полный размер массива для temp, даже когда используется только небольшая часть temp. Вы можете изменить это на: 

int k = 0;
...
int temp[fin+1-deb];
...
tab[i]=temp[i-deb];

все равно это будет превышать пространство стека, если n большое. Так как предложено в других ответах: 

int k = 0;
...
int *temp = malloc((fin+1-deb)*sizeof(int));
...
tab[i]=temp[i-deb];
...
free(temp)

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

1 голос
/ 02 апреля 2019

(Примечание: опубликовано после ответа от @Eric Postpischil).

Функция 

void fusion(int * tab, int deb, int mid, int fin)

Имеет линию 

int temp[fin+1];

и значение fin поступает через другую функцию из числа элементов n, которые должны быть отсортированы 

triFusion(tab, 0, n-1);

и, как автоматическая переменная, разбивает стек, если n велико.

Я предлагаю заменить строку на 

int *temp = malloc((fin+1) * sizeof *temp);
if(temp == NULL) {
    puts("malloc");
    exit(1);
}

// ...

free(temp);
...