Сортировка слиянием не работает для таблицы целых чисел с более чем 521096 элементов - PullRequest
Новая
       15

Сортировка слиянием не работает для таблицы целых чисел с более чем 521096 элементов

1 голос
/ 10 октября 2019

Я пытаюсь отсортировать большую таблицу целых чисел, используя различные типы алгоритмов сортировки, такие как быстрая сортировка, сортировка по пузырькам и сортировка слиянием, все эти алгоритмы работают просто отлично. Тем не менее, при попытке сортировки таблицы с более чем 521096 элементами с использованием сортировки слиянием программа просто завершает работу без каких-либо ошибок (я предполагаю, что в C это ошибка времени выполнения)

Обратите внимание, что сортировка слиянием работаетидеально с таблицей, которая содержит менее 921096 элементов. Также обратите внимание, что, например, быстрая сортировка отлично работает с таблицами любой длины (я пробовал до 1 миллиона элементов).

Вот код, который я использую: 

void fillTable(int *t,int n){
    srand(time(NULL));
    int signe=1;
    for(int *p=t;p<t+n;p++){
        *(p)=signe*rand()%n;
        signe*=-1;
    }
}
void mergeTables(int *tab,int l,int m,int r){
    int i,j,k;
    int n1=m-l+1;
    int n2=r-m; 


    int lTab[n1],rTab[n2];

    for(i=0;i<n1;i++){
        lTab[i]=tab[l+i];
    }
    for(i=0;i<n2;i++){
        rTab[i]=tab[m+1+i];
    }

    i=0;j=0;k=l;
    while(i<n1 && j<n2){
        if(lTab[i]<=rTab[j]){
            tab[k]=lTab[i];
            i++;
        }
        else{
            tab[k]=rTab[j];
            j++;
        }
        k++;
    }
    while(i<n1){
        tab[k]=lTab[i];
        i++;
        k++;
    }
    while(j<n2){
        tab[k]=rTab[j];
        j++;
        k++;
    }
}

void diviserTab(int *tab,int l,int r){
    if(r>l){
        int m=(r+l)/2;
        diviserTab(tab,l,m);
        diviserTab(tab,m+1,r);
        mergeTables(tab,l,m,r);
    }
}
void mergeSort(int* t,int n){
        diviserTab(t,0,n-1);
}
double getTime(void(*f)(int*,int),int* t,int n){
    clock_t start,end;
    start=clock();
    f(t,n);
    end=clock();
    return (double)(end-start)/CLOCKS_PER_SEC;
}

и вот мой главный: 

int main(){

int *tab;
int i;
int n=521096;
tab=(int*)malloc(n*sizeof(int));
fillTable(tab,n);
printf("First 10 elements before sorting");
for ( i = 0; i < 10; i++)
{
    printf("%5d\t",tab[i]);
}

printf("%f\n",getTime(mergeSort,tab,n));
printf("\nFirst 10 elements before sorting\n");
for ( i = 0; i < 10; i++)
{
    printf("%5d\t",tab[i]);
}


return 0;

}

Теперь к результатам: если n = 521095 (количество элементов в массиве) 

First 10 elements before sorting
18187   -12205  23363   -27523  30572   -31906   5475   -10341   5178   -27678
it took 0.179000 to sort the array

First 10 elements after sorting
-32767  -32767  -32767  -32767  -32767  -32767  -32767  -32766  -32766  -32766

если n= 521096 

First 10 elements before sorting
18243   -31088  32141   -10616   9312    -356   25619   -26113  23731   -21465

(и он просто выходит)

1 Ответ

2 голосов
/ 10 октября 2019

Вы выделяете несколько больших массивов в стеке. Из вашей mergeTables функции: 

int lTab[n1],rTab[n2];

С большим массивом для сортировки n1 и n2, и, следовательно, lTab и rTab, могут стать большими (вдвое меньше вашегоначальный массив), а стек обычно довольно мал. Если массивы не подходят, могут происходить всякие странные вещи. Когда я попробовал вашу программу с большим массивом (10 миллионов целых чисел), программа упала.

Быстрая сортировка и пузырьковая сортировка обычно выполняются на месте, поэтому я предполагаю, что вам не нужно все это дополнительное пространство для них.

Я изменил ваши два массива на это: 

int *lTab = malloc(n1 * sizeof(int));
int *rTab = malloc(n2 * sizeof(int));

А затем в конце функции: 

free(lTab);
free(rTab);
...