C-铲斗排序中的分割故障 插入排序算法

Question

我想知道为什么我为存储桶排序实现的算法会因此而得出细分故障。似乎实施中的所有内容都很好地工作了，但是可能有一些变量n应该是n 1或其他。我遇到了一些困难。

我正在根据此视频中描述的内容实施。

#include <stdio.h>
#include <stdlib.h>
void insertion(int * array, int n){
    // insertion sort
    int i = 1, j = 0, temp;
    while(i < n){
        j = i;
        while(j > 0 && array[j-1] > array[j]){
            temp = array[j-1];
            array[j-1] = array[j];
            array[j] = temp;
            --j;
        }
        ++i;
    }
}
void bucket(int * array, int n){
    int max,i,j,k,size, div, pos;
    int ** buckets, *bucket_position;
    //Find maximum value in array
    max = array[0];
    for(i=0;i<n;++i) if( max < array[i] ) max = array[i];
    //Determine amount of buckets and creates them
    size = max / n;
    buckets = (int**) malloc(sizeof(int*) * size);
    for(i=0;i<size;++i){
        buckets[i] = (int*) malloc(sizeof(int) * max);
    }
    bucket_position = (int*) malloc(sizeof(int) * size);
    for(i=0;i<size;++i) bucket_position[i] = 0;
    //Copy array values into the buckets
    div = (max+1) / size;
    if( (max+1) % size ) ++div;
    for(i=0;i<n;++i){
        pos = array[i] / div;
        buckets[pos][bucket_position[pos]] = array[i];
        ++bucket_position[pos];
    }
    //Take values out of the buckets into the array
    k = 0;  
    for(i=0;i<size;++i){
        for(j=0;j<=bucket_position[i];++j){
            array[k] = buckets[i][j];
            ++k;
        }
    }
    //Do insertion sort over the array
    insertion(array,n);
}
int main(){
    int array[5] = {24354,95023,439052,934851};
    int n = 5;
    bucket(array,n);
    return 0;
}

程序输出是分割故障而不是排序的数组。

Answer 1

您想用n == 5元素对数组进行排序，其最大vlaue是：

max == 934851

然后您计算出桶的nuber：

size = max / n == 186970

现在，您尝试为186970桶分配内存，每个存储桶有能力保存934851元素：

buckets = (int**) malloc(sizeof(int*) * size);
for (i = 0; i < size; ++i) {
    buckets[i] = (int*) malloc(sizeof(int) * max);
}

大约是651 GB。有了如此多的大型分配，系统可能无法提供更多的内存。因此，您应该检查从malloc返回的指针是NULL。这就是发生的：您的数组索引是合法的，但是动态分配的数组是NULL。

当然，您不需要太多的内存即可对五个元素进行排序。对于如此小的阵列，您根本不需要使用水桶；立即使用插入排序。

对于较大的数组，将存储桶数的数量基于元素数量，而不是最大值。在最坏的情况下，所有元素都进入一个水桶，然后将其具有n元素。因此，您也不需要max来确定此处的大小。

但是，您应该使用您的程序没有的max和min来计算存储桶索引：

index = (a[i] - min) * nbuckets / (max + 1 - min)

请注意此处可能的算术溢出。（+ 1确保最大元素无法获得无效的索引n。）

Answer 2

此代码

k = 0;  
for(i=0;i<size;++i){
    for(j=0;j<=bucket_position[i];++j){
        array[k] = buckets[i][j];
        ++k;
    }
}

是一个问题。

您会多次增加k，从而在array之外写入。请记住，k的有效范围仅为0到4。

而不是

for(j=0;j<=bucket_position[i];++j){
        ^^^^

也许你想要

for(j=0;j<bucket_position[i];++j){
        ^^^

即。<而不是<=，以便您不会在每个循环中增加k。