Сортировка по основанию для массива 10 ^ 6 в C

у меня есть этот код, и он падает в середине обработки. Система выдает сообщение «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;
}

Вот еще один код, который я попробовал, на этот раз я использовал malloc. Но все равно вылетает перед началом сортировки. все в порядке, если количество элементов ‹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;
}

c radix-sort
person rimasbimas    schedule 31.03.2015    source источник
comment
Локальные переменные обычно хранятся в стеке, а размер стека обычно ограничен однозначной цифрой в мегабайтах. Например, в Windows значение по умолчанию составляет 1 МБ на процесс, а в Linux — 8 МБ. Вы используете 4000000 байтов для массива b в функции radix_sort, поэтому, если вы работаете в Windows, вы превысили лимит.   -  person Some programmer dude    schedule 31.03.2015
comment
Кстати, массив распадается на указатели на их первый элемент, например, при передаче в функции. Так что &arr[0] ничем не отличается от arr.   -  person Some programmer dude    schedule 31.03.2015

Ответы (1)


arrow_upward
0
arrow_downward

Ошибка здесь:

 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);
}
person chqrlie    schedule 31.03.2015
comment
6 ошибок и 6 предупреждений в этой функции. - person rimasbimas; 31.03.2015
comment
Ваш первый совет, где ошибка помогла мне :) Спасибо - person rimasbimas; 31.03.2015
comment
@rimasbimas: я добавил недостающие #include <stdlib.h> и пару {}. Можете ли вы сказать мне, какой компилятор вы используете и какие ошибки и предупреждения вы получаете? - person chqrlie; 31.03.2015