Следующая программа предназначена для сортировки большого массива случайных чисел с помощью heapsort. Результатом работы программы является общее время выполнения рекурсивной функции heapSort (в микросекундах). Размер входного массива определяется макросом SIZE.
Программа отлично работает для SIZE до 1 миллиона (1000000). Но когда я пытаюсь выполнить программу с размером SIZE 10 миллионов (10000000), программа генерирует ошибку сегментации (дамп ядра).
Примечание. Я уже пытался увеличить мягкие и жесткие пределы стека с помощью команды ulimit -s в Linux (128 МБ). SEGFAULT все еще сохраняется.
Пожалуйста, предложите мне любые изменения необходимого кода или любой метод, который преодолеет существующую болезнь SEGFAULT без необходимости объявлять массив динамически или как глобальный/статический. /* Программа для реализации алгоритма Heap-Sort */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
long SIZE = 10000000; // Or #define SIZE 10000000
long heapSize;
void swap(long *p, long *q)
{
long temp = *p;
*p = *q;
*q = temp;
}
void heapify(long A[], long i)
{
long left, right, index_of_max;
left = 2*i + 1;
right = 2*i + 2;
if(left<heapSize && A[left]>A[i])
index_of_max = left;
else
index_of_max = i;
if(right<heapSize && A[right]>A[index_of_max])
index_of_max = right;
if(index_of_max != i)
{
swap(&A[index_of_max], &A[i]);
heapify(A, index_of_max);
}
}
void buildHeap(long A[])
{
long i;
for(i=SIZE/2; i>=0 ; i--)
heapify(A,i);
}
void heapSort(long A[])
{
long i;
buildHeap(A);
for(i=SIZE-1 ; i>=1 ; i--)
{
swap(&A[i], &A[0]);
heapSize--;
heapify(A, 0);
}
}
int main()
{
long i, A[SIZE];
heapSize = SIZE;
struct timespec start, end;
srand(time(NULL));
for(i = 0; i < SIZE; i++)
A[i] = rand() % SIZE;
/*printf("Unsorted Array is:-\n");
for(i = 0; i < SIZE; i++)
printf("%li\n", A[i]);
*/
clock_gettime(CLOCK_MONOTONIC_RAW, &start);//start timer
heapSort(A);
clock_gettime(CLOCK_MONOTONIC_RAW, &end);//end timer
//To find time taken by heapsort by calculating difference between start and stop time.
unsigned long delta_us = (end.tv_sec - start.tv_sec) * 1000000 \
+ (end.tv_nsec - start.tv_nsec) / 1000;
/*printf("Sorted Array is:-\n");
for(i = 0; i < SIZE; i++)
printf("%li\n", A[i]);
*/
printf("Heapsort took %lu microseconds for sorting of %li elements\n",delta_us, SIZE);
return 0;
}
malloc()
или что-то подобное. - person Jonathan Leffler   schedule 01.03.2018