Radix sort для массива 10^6 в C

Question

У меня есть этот код, и он падает в середине обработки. Система выдает сообщение «filename.exe перестал работать. Что здесь не так? Я объявляю массив как глобального, чтобы быть в состоянии иметь такое большое количество элементов, но до сих пор она не работает.

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

#define MAX 1000000 
#define SHOWPASS 

void print(int *a, int n) { 
int i; 
for (i = 0; i < n; i++) 
    printf("%d\t", a[i]); 
} 

void radix_sort(int *a, int n) { 
int i, b[MAX], m = 0, exp = 1; 
for (i = 0; i < n; i++) { 
    if (a[i] > m) 
    m = a[i]; 
} 

while (m/exp > 0) { 
    int box[10] = { 0 }; 
    for (i = 0; i < n; i++) 
    box[a[i]/exp % 10]++; 
    for (i = 1; i < 10; i++) 
    box[i] += box[i - 1]; 
    for (i = n - 1; i >= 0; i--) 
    b[--box[a[i]/exp % 10]] = a[i]; 
    for (i = 0; i < n; i++) 
    a[i] = b[i]; 
    exp *= 10; 

#ifdef SHOWPASS 
    printf("\n\nPASS : "); 
    print(a, n); 
#endif 
} 
} 
int arr[MAX]; 
int main() { 
//int arr[MAX]; 
int i, num; 

printf("\nEnter total elements (num < %d) : ", MAX); 
scanf("%d", &num); 

printf("\ncreate array : "); 
for (i = 0; i < num; i++) 
    arr[i]=rand()%10; 

printf("\nARRAY : "); 
print(&arr[0], num); 

radix_sort(&arr[0], num); 

printf("\n\nSORTED : "); 
print(&arr[0], num); 

return 0; 
} 

Вот еще .. код я пытался, на этот раз я использовал таНос Но все же он выходит из строя, прежде чем начать сортировать все в порядке, если число элементов < 100000.

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

#define MAX 1000000 
#define SHOWPASS 

void print(int *a, int n) { 
int i; 
for (i = 0; i < n; i++) 
    printf("%d\t", a[i]); 
} 

void radix_sort(int *a, int n) { 
int i, b[MAX], m = 0, exp = 1; 
for (i = 0; i < n; i++) { 
    if (a[i] > m) 
    m = a[i]; 
} 

while (m/exp > 0) { 
    int box[10] = { 0 }; 
    for (i = 0; i < n; i++) 
    box[a[i]/exp % 10]++; 
    for (i = 1; i < 10; i++) 
    box[i] += box[i - 1]; 
    for (i = n - 1; i >= 0; i--) 
    b[--box[a[i]/exp % 10]] = a[i]; 
    for (i = 0; i < n; i++) 
    a[i] = b[i]; 
    exp *= 10; 

#ifdef SHOWPASS 
    printf("\n\nPASS : "); 
    print(a, n); 
#endif 
} 
} 

int i, num; 
int main() { 

int* arr = (int*)malloc(MAX * sizeof(int)); 
int i; 

printf("\ncreate array : "); 
for (i = 0; i < MAX; i++) 
    arr[i]=rand()%10; 

printf("\nARRAY : "); 
print(&arr[0], MAX); 

radix_sort(&arr[0], MAX); 

printf("\n\nSORTED : "); 
print(&arr[0], MAX); 
free(arr); 
return 0; 
} 

Answer 1

эта ошибка здесь:

int i, b[MAX], m = 0, exp = 1; 

Выделение огромного массива (1 млн. int) в стеке невозможно в некоторых, если не в большинстве систем.

Вы должны указать malloc временный массив и выделить только размер, необходимый для сортировки, а именно n * sizeof(int).

Другая проблема заключается в следующем: ваш radix_sort не может обрабатывать отрицательные числа.

Менее важно, но стоит упомянуть: ваша реализация нестабильна. Не проблема для простых массивов int, но потенциально некорректная для больших структур.

Кроме того, ваш код неэффективен: вы используете деление и по модулю 10. Было бы гораздо быстрее использовать смену и маскировку.

Вот более эффективная реализация для больших массивов:

#include <limits.h> 
#include <string.h> 
#include <stdlib.h> 

static void radix_sort(int *a, size_t size) { 
    size_t counts[sizeof(*a)][256] = {{ 0 }}, *cp; 
    size_t n, i, sum; 
    unsigned int *tmp, *src, *dst, *aa; 

    dst = tmp = malloc(size * sizeof(*a)); 
    src = (unsigned int *)a; 
    for (i = 0; i < size; i++) { 
     unsigned int v = src[i] + (unsigned int)INT_MIN; 
     for (n = 0; n < sizeof(*a) * 8; n += 8) 
      counts[n >> 3][(v >> n) & 255]++; 
    } 
    for (n = 0; n < sizeof(*a) * 8; n += 8) { 
     cp = &counts[n >> 3][0]; 
     if (cp[0] == size) continue; 
     for (i = sum = 0; i < 256; i++) 
      cp[i] = (sum += cp[i]) - cp[i]; 
     for (i = 0; i < size; i++) 
      dst[cp[((src[i] + (unsigned int)INT_MIN) >> n) & 255]++] = src[i]; 
     aa = src; 
     src = dst; 
     dst = aa; 
    } 
    if (src == tmp) { 
     memcpy(a, src, size * sizeof(*a)); 
    } 
    free(tmp); 
}