基数排序在C 10 ^ 6阵列 [英] Radix sort for 10^6 array in C
问题描述
我有这个code和它在处理过程中崩溃。系统给出信息文件名.exe停止工作。什么是错在这里？
我声明数组作为全球能有元素的那么大数目，但它仍然无法正常工作。
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;＃定义MAX百万
＃定义SHOWPASS无效打印（INT *一，INT N）{
INT I;
对于（i = 0; I＆LT; N;我++）
的printf（％d个\\ t的，一个[我]）;
}无效radix_sort为（int *一，INT N）{
INT I，B [MAX]，m = 0时，实验值= 1;
对于（i = 0; I＆LT; N;我++）{
如果（一个[Ⅰ]≥米）
M =一个由[i];
} 而（米/ EXP大于0）{
INT盒[10] = {0};
对于（i = 0; I＆LT; N;我++）
盒[A [I] / EXP％10] ++;
为（ⅰ= 1; I＆小于10;我+ +）
盒[I] + =盒[我 - 1];
对于（i = N - 1; I＆GT; = 0;我 - ）
B〔 - 盒[A [I] / EXP％10] = a [i];
对于（i = 0; I＆LT; N;我++）
一个由[i] = B [I];
EXP * = 10;#IFDEF SHOWPASS
的printf（\\ n \\ nPASS：）;
打印（A，N）;
＃万一
}
}
INT ARR [MAX];
诠释主（）{
// INT ARR [MAX];
INT I，NUM; 的printf（\\ n输入总单元（NUM＆LT;％D）：MAX）;
scanf函数（％D，试验＃）; 的printf（\\ n创建数组：）;
对于（i = 0; I＆LT;民;我++）
改编[I] =兰特（）％10; 的printf（\\ nARRAY：）;
打印（安培;常用3 [0]，NUM）; radix_sort（安培;常用3 [0]，NUM）; 的printf（\\ n \\ nSORTED：）;
打印（安培;常用3 [0]，NUM）; 返回0;
}
下面是另一个code我想，这次我使用的malloc。但它仍然开始排序之前崩溃。一切都很好，如果元素的个数为＆lt; 100000
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;＃定义MAX百万
＃定义SHOWPASS无效打印（INT *一，INT N）{
INT I;
对于（i = 0; I＆LT; N;我++）
的printf（％d个\\ t的，一个[我]）;
}无效radix_sort为（int *一，INT N）{
INT I，B [MAX]，m = 0时，实验值= 1;
对于（i = 0; I＆LT; N;我++）{
如果（一个[Ⅰ]≥米）
M =一个由[i];
} 而（米/ EXP大于0）{
INT盒[10] = {0};
对于（i = 0; I＆LT; N;我++）
盒[A [I] / EXP％10] ++;
为（ⅰ= 1; I＆小于10;我+ +）
盒[I] + =盒[我 - 1];
对于（i = N - 1; I＆GT; = 0;我 - ）
B〔 - 盒[A [I] / EXP％10] = a [i];
对于（i = 0; I＆LT; N;我++）
一个由[i] = B [I];
EXP * = 10;#IFDEF SHOWPASS
的printf（\\ n \\ nPASS：）;
打印（A，N）;
＃万一
}
}INT I，NUM;
诠释主（）{为int * ARR =（INT *）malloc的（MAX *的sizeof（INT））;
INT I; 的printf（\\ n创建数组：）;
对于（i = 0; I＆LT; MAX;我++）
改编[I] =兰特（）％10; 的printf（\\ nARRAY：）;
打印（安培;常用3 [0]，MAX）; radix_sort（安培;常用3 [0]，MAX）; 的printf（\\ n \\ nSORTED：）;
打印（安培;常用3 [0]，MAX）;
免费（ARR）;
返回0;
}
该错误是在这里：
INT I，B [MAX]，M = 0，指数= 1;
分配一个巨大的（100万 INT ）堆栈上的数组是不可能的一些如果不是大多数的系统。
您应该的malloc 临时数组并分配只需要排序的大小，即 N * sizeof的（INT）。
另外一个问题是这样的：你的 radix_sort 不能处理负数
不太重要，但值得一提的：你的实现并不稳定。不是一个简单的 INT 数组的问题，但可能不正确的较大的结构。
此外，您的code是低效的：你用除法和模数10，这将是更快使用移位和屏蔽
。下面是对于大数组更有效的实现：
的#include＆LT;＆limits.h中GT;
＃包括LT＆;＆string.h中GT;
＃包括LT＆;＆stdlib.h中GT;静态无效radix_sort为（int *一，为size_t大小）{
为size_t计数[的sizeof（* A）] [256] = {{0}} * CP;
为size_t N，I，总和;
无符号整型* TMP，* SRC，DST *，* AA; DST = TMP =的malloc（大小*的sizeof（* a）条）;
SRC =（unsigned int类型*）一个;
对于（i = 0; I＆LT;大小;我++）{
unsigned int类型V = SRC [I] +（无符号整数）INT_MIN;
为（n = 0时; N＆下;的sizeof（*一）* 8; N + = 8）
计数[N＆GT;＆GT; 3] [（V＆GT;将N）及255] ++;
}
为（n = 0时; N＆下;的sizeof（*一）* 8; N + = 8）{
CP =＆放大器;计数[N＆GT;＆GT; 3] [0];
如果（CP [0] ==大小）继续;
对于（i =总和= 0; I＆LT; 256;我++）
CP [I] =（总和+ = CP [I]） - CP [I]
对于（i = 0; I＆LT;大小;我++）
DST [CP [（（SRC [I] +（无符号整数）INT_MIN）GT;＆GT; N）及255] ++] = SRC [I]
AA = SRC;
SRC = DST;
DST = AA;
}
如果（SRC == TMP）{
的memcpy（一，SRC，尺寸*的sizeof（* a）条）;
}
免费（TMP）;
}
i have this code and it crash in the middle of processing. System gives message "filename.exe stopped working. What is wrong here? I declare array as global to be able to have so big number of elements, but still it doesn't work.
#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;
}
Here is another code i tried, this time i used malloc. But still it crashes before starting sort. everything is fine if number of elements is <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;
}
The bug is here:
int i, b[MAX], m = 0, exp = 1;
Allocating a huge (1 million int) array on the stack is not possible on some if not most systems.
You should malloc the temporary array and allocate only the size needed for the sort, namely n * sizeof(int).
Another problem is this: your radix_sort cannot handle negative numbers.
Less important but worth mentioning: your implementation is not stable. Not a problem for simple int arrays, but potentially incorrect for larger structures.
Furthermore, your code is inefficient: you use division and modulo 10. It would be much faster to use shifting and masking.
Here is a more efficient implementation for large arrays:
#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);
}
这篇关于基数排序在C 10 ^ 6阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
