Сортировка больших массивов (QuickSort) - ошибка сегментации

Question

Для этой программы я создаю массив случайных целых чисел, разделяя этот массив на две или четыре части, сортируя каждую часть и объединяя их обратно в отсортированный массив. Часть сортировки вставки программы работает для размера массивов, которые мне нужны. Проблема заключается в быстрой сортировке. Он работает только с массивами размером до 3 миллионов целых чисел. Мне нужно, чтобы он работал с массивами размером до 100 миллионов целых чисел. В настоящее время выше 3 миллионов это дает мне ошибку «ошибка сегментации (core dumped)». Под этим 3 миллиона это работает. Кто-нибудь видит проблему? Я предполагаю, что что-то переполнено. Если вы посмотрите ниже, вы можете увидеть несколько объявлений malloc, мою попытку устранить проблему. Это не работает.

Редактировать: Я немного отлаживал и прокомментировал содержимое части «if (s_type ==« Q ») моего кода. Он по-прежнему дал мне ошибку сегментации для большого массива.

void insertion_sort (int ar[], int size) { 
    int c, d, t; 
    for (c = 1; c <= size - 1; c++){ 
     d = c; 

     while(d > 0 && ar[d] < ar[d - 1]) { 
      t = ar[d]; 
      ar[d] = ar[d - 1]; 
      ar[d - 1] = t; 

      d--; 
     } 
    } 
} 

void quick_sort (int *a, int n) { 
    int i, j, p, t; 
    if(n < 2) 
     return; 
    p = a[n/2]; 
    for (i = 0, j = n - 1;; i++, j--) { 
     while (a[i] < p) 
      i++; 
     while (p < a[j]) 
      j--; 
     if (i >= j) 
      break; 
     t = a[i]; 
     a[i] = a[j]; 
     a[j] = t; 
     } 
     quick_sort(a, i); 
     quick_sort(a + i, n - i); 
} 

void check_sort (int ara[], int size_t) { 
    int b; 
    int c_i; 

    c_i = 0; 

    for (b = 1; b < size_t; b++) { 
     if (ara[b - 1] > ara[b]) { 
      printf("Array is not sorted correctly\n"); 
      break; 
     } else { 
      c_i++; 
     } 
    } 

    if (c_i == size_t - 1) { 
     printf("Array is sorted correctly\n"); 
    } 
} 

void combine_array(int a_ar[], int b_ar[], int c_ar[], int size_1, int size_2) { 
    int i, j, k; 
    i = 0; 
    j = 0; 
    k = 0; 

    while (i < size_1 && j < size_2) { 
     if (a_ar[i] < b_ar[j]) { 
      c_ar[k] = a_ar[i]; 
      i++; 
     } else { 
      c_ar[k] = b_ar[j]; 
      j++; 
     } 
     k++; 
    } 

    if (i >= size_1) { 
     while (j < size_2) { 
      c_ar[k] = b_ar[j]; 
      j++; 
      k++; 
     } 
    } 

    if (j >= size_2) { 
     while (i < size_1) { 
      c_ar[k] = a_ar[i]; 
      i++; 
      k++; 
     } 
    } 
} 

long gRefTime; 

long GetMilliSecondTime(struct timeb timeBuf) { 
    long mliScndTime; 
    mliScndTime = timeBuf.time; 
    mliScndTime *= 1000; 
    mliScndTime += timeBuf.millitm; 
    return mliScndTime; 
} 

long GetCurrentTime(void) { 
    long crntTime=0; 
    struct timeb timeBuf; 
    ftime(&timeBuf); 
    crntTime = GetMilliSecondTime(timeBuf); 
    return crntTime; 
} 

void SetTime(void) { 
    gRefTime = GetCurrentTime(); 
} 

long GetTime(void) { 
    long crntTime = GetCurrentTime(); 
    return (crntTime - gRefTime); 
} 

int main (int argc, char *argv[]) { 
    int a_size, t_num; 
    char s_type; 
    int i, j, k; 
    int two_s[1]; 
    int four_s[3]; 

    a_size = atoi(argv[1]); 
    t_num = atoi(argv[2]); 
    s_type = argv[3][0]; 

    pthread_t tid[t_num]; 
    pthread_attr_t attr;  

    struct sort_2 { 
     int array_ss[(a_size/2)]; 
     int arr_s; 
    }; 

    struct sort_2 firstS; 
    struct sort_2 firstS1; 

    int *array_m = malloc(a_size * sizeof(*array_m)); 

    for (i = 0; i < a_size; i++) { 
     array_m[i] = rand(); 
    } 

    //for (i = 0; i < a_size; i++) { 
     //printf("%d \n", array_m[i]); 
    //} 

    printf("\n"); 

    if (t_num == 2) { 
     two_s[0] = ((a_size/2)); 
     two_s[1] = (a_size); 
     int *array_s1 = malloc(two_s[0] * sizeof(*array_s1)); 
     int *array_s2 = malloc(two_s[0] * sizeof(*array_s2)); 

     printf("First half \n"); 

     for (j = 0; j < two_s[0]; j ++) { 
      array_s1[j] = array_m[j]; 
      //printf("%d \n", array_s1[j]); 
     } 

     printf("Second half \n"); 

     for (k = two_s[0]; k < two_s[1]; k++) { 
      array_s2[k - two_s[0]] = array_m[k]; 
      //printf("%d \n", array_s2[k - two_s[0]]); 
     } 

    printf("\n"); 

    check_sort(array_m, a_size); 

    if (s_type == 'I') { //Insertion sort 

     SetTime(); 

     insertion_sort(array_s1, two_s[0]); 
     insertion_sort(array_s2, two_s[0]); 

     printf("Sorted first half \n"); 

     for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s1[i]); 
     } 

     printf("Sorted second half \n"); 

     for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s2[i]); 
     }  

     combine_array(array_s1, array_s2, array_m, two_s[0], two_s[0]); 

     printf("Time to sort and combine: %f \n", (GetTime())); 

     printf("\n"); 

     printf("Combined and sorted sequentially via Insertion Sort \n"); 

     for (i = 0; i < a_size; i++) { 
      //printf("%d \n", array_m[i]); 
     } 

     check_sort(array_m, a_size); 

     //Start of thread section 

     for (i = 0; i < a_size; i++) { 
      array_m[i] = rand(); 
     } 

     printf("First half \n"); 

     for (j = 0; j < two_s[0]; j ++) { 
      array_s1[j] = array_m[j]; 
      firstS.array_ss[j] = array_s1[j]; 
     } 

     firstS.arr_s = two_s[0]; 

     printf("Second half \n"); 

     for (k = two_s[0]; k < two_s[1]; k++) { 
      array_s2[k - two_s[0]] = array_m[k]; 
      firstS1.array_ss[k] = array_s2[k - two_s[0]]; 
     } 

     firstS1.arr_s = two_s[0]; 

     //pthread_attr_init(&attr); 
     //pthread_create(&tid, &attr, insertion_sort, *firstS);   
    } 

    if (s_type == 'Q') { //Quick sort 

     SetTime(); 

     quick_sort(array_s1, two_s[0]); 
     quick_sort(array_s2, two_s[0]); 

     printf("Sorted first half \n"); 

     for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s1[i]); 
     } 

     printf("Sorted second half \n"); 

     for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s2[i]); 
     }  

     combine_array(array_s1, array_s2, array_m, two_s[0], two_s[0]); 

     printf("Time to sort and combine: %f \n", (GetTime())); 

     printf("\n"); 

     printf("Combined and sorted sequentially via Quick Sort \n"); 

     for (i = 0; i < a_size; i++) { 
      //printf("%d \n", array_m[i]); 
     } 

     check_sort(array_m, a_size); 

     for (i = 0; i < a_size; i++) { 
      array_m[i] = rand(); 
     }  
    } 
    } 

    //Four part array 

    if (t_num == 4) { 
     two_s[0] = ((a_size/2)); 
     two_s[1] = (a_size); 
     four_s[0] = ((a_size/4)); 
     //two_s[1] = (a_size); 
     int *array_s14 = malloc(four_s[0] * sizeof(array_s14)); 
     int *array_s24 = malloc(four_s[0] * sizeof(array_s24)); 
     int *array_s34 = malloc(four_s[0] * sizeof(array_s34)); 
     int *array_s44 = malloc(four_s[0] * sizeof(array_s44)); 
     int *array_14 = malloc(two_s[0] * sizeof(array_14)); 
     int *array_24 = malloc(two_s[0] * sizeof(array_24)); 

     printf("First quarter \n"); 

     for (j = 0; j < four_s[0]; j++) { 
      array_s14[j] = array_m[j]; 
      //printf("%d \n", array_s14[j]); 
     } 

     printf("Second quarter \n"); 

     for (k = 0; k < four_s[0]; k++) { 
      array_s24[k] = array_m[k + four_s[0]]; 
      //printf("%d \n", array_s24[k]); 
     } 

     printf("Third quarter \n"); 

     for (j = 0; j < four_s[0]; j++) { 
      array_s34[j] = array_m[j + (2 * four_s[0])]; 
      //printf("%d \n", array_s34[j]); 
     } 

     printf("Fourth quarter \n"); 

     for (k = 0; k < four_s[0]; k++) { 
      array_s44[k] = array_m[k + (3 * four_s[0])]; 
      //printf("%d \n", array_s44[k]); 
     } 

    printf("\n"); 

    check_sort(array_m, a_size); 

    if (s_type == 'I') { //Insertion sort 

     SetTime(); 

     insertion_sort(array_s14, four_s[0]); 
     printf("Sorted first quarter \n"); 
     insertion_sort(array_s24, four_s[0]); 
     printf("Sorted second quarter \n"); 
     insertion_sort(array_s34, four_s[0]); 
     printf("Sorted third quarter \n"); 
     insertion_sort(array_s44, four_s[0]); 
     printf("Sorted fourth quater \n");  

     //printf("Sorted first half \n"); 

     //for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s1[i]); 
     //} 

     //printf("Sorted second half \n"); 

     //for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s2[i]); 
     //}  

     combine_array(array_s14, array_s24, array_14, four_s[0], four_s[0]); 
     combine_array(array_s34, array_s44, array_24, four_s[0], four_s[0]); 
     combine_array(array_14, array_24, array_m, two_s[0], two_s[0]); 

     printf("Time to sort and combine: %f \n", (GetTime())); 

     printf("\n"); 

     printf("Combined and sorted sequentially via Insertion Sort \n"); 

     for (i = 0; i < a_size; i++) { 
      //printf("%d \n", array_m[i]); 
     } 

     check_sort(array_m, a_size); 

     //Start of thread section 

/*  for (i = 0; i < a_size; i++) { 
      array_m[i] = rand(); 
     } 

     printf("First half \n"); 

     for (j = 0; j < two_s[0]; j ++) { 
      array_s1[j] = array_m[j]; 
      firstS.array_ss[j] = array_s1[j]; 
     } 

     firstS.arr_s = two_s[0]; 

     printf("Second half \n"); 

     for (k = two_s[0]; k < two_s[1]; k++) { 
      array_s2[k - two_s[0]] = array_m[k]; 
      firstS1.array_ss[k] = array_s2[k - two_s[0]]; 
     } 

     firstS1.arr_s = two_s[0]; */ 

     //pthread_attr_init(&attr); 
     //pthread_create(&tid, &attr, insertion_sort, *firstS);   
    } 

    if (s_type == 'Q') { //Quick sort 

     SetTime(); 

     quick_sort(array_s14, four_s[0]); 
     printf("Sorted first quarter \n"); 
     quick_sort(array_s24, four_s[0]); 
     printf("Sorted second quarter \n"); 
     quick_sort(array_s34, four_s[0]); 
     printf("Sorted third quarter \n"); 
     quick_sort(array_s44, four_s[0]); 
     printf("Sorted fourth quarter \n");  

/*  printf("Sorted first half \n"); 

     for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s1[i]); 
     } 

     printf("Sorted second half \n"); 

     for (i = 0; i < two_s[0]; i++) { 
      //printf("%d \n", array_s2[i]); 
     } */ 

     combine_array(array_s14, array_s24, array_14, four_s[0], four_s[0]); 
     combine_array(array_s34, array_s44, array_24, four_s[0], four_s[0]); 
     combine_array(array_14, array_24, array_m, two_s[0], two_s[0]); 

     printf("Time to sort and combine: %f \n", (GetTime())); 

     printf("\n"); 

     printf("Combined and sorted sequentially via Quick Sort \n"); 

     for (i = 0; i < a_size; i++) { 
      //printf("%d \n", array_m[i]); 
     } 

     check_sort(array_m, a_size); 

     for (i = 0; i < a_size; i++) { 
      array_m[i] = rand(); 
     }  
    } 
    } 

} 

Answer 1

Я вижу две ошибки здесь, первый: Вы не проверить значение ARGC перед использованием ARGV. Если вы не передадите аргументы в вашу программу, вы в конечном итоге отправки неопределенные адреса в atoi здесь:

a_size = atoi(argv[1]); 
t_num = atoi(argv[2]); 

Второй:

a_size = atoi(argv[1]); 

atoi() возвращает Int, который не может быть выше до 2147483647 (2^31), в противном случае она переливается и в конечном итоге ниже 0.

Answer 2

struct sort_2 { 
    int array_ss[(a_size/2)]; 
    int arr_s; 
}; 

struct sort_2 firstS; 
struct sort_2 firstS1; 

Здесь, a_size = 3 000 000, вы просите 12Мб оперативной памяти в стеке, которым вызывает вашу программу к stackoverflow, я предлагаю yo u используйте malloc().

Answer 3

Возможно, эта программа не будет работать на вашем компьютере, если она имеет 32-битную архитектуру. Я думаю, что вы не можете иметь непрерывный массив размером более 4 ГБ в такой машине. На шахте он работает отлично:

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

#define N 10000000000UL 

typedef int T; 

int compare(const void *_a, const void *_b) 
{ 
    const T *a = _a, *b = _b; 
    if (*a > *b) return 1; 
    if (*a < *b) return -1; 
    return 0; 
} 

int main() 
{ 
    T *b; 
    int i; 

    printf("Trying %lld array (%lld bytes)\n", 
      (long long)N, (long long) sizeof(T) * N); 
    assert(b = malloc(sizeof(T) * N)); 
    printf("b = %#p\n", b); 
    printf("filling\n"); 
    for (i = 0; i < N; i++) 
     b[i] = rand(); 
    printf("quicksorting\n"); 
    qsort(b, N, sizeof(T), compare); 
    for (i = 0; i < N; i++) 
     printf("a[%d] = %d\n", i, b[i]); 
} 

Вы можете играть с различными значениями N и T.