我正在尝试在 C 中将 qsort algortihm 实现为通用函数

I am trying to implement qsort algortihm as a generic function in C

提问人:Alexandra Turner 提问时间:11/17/2023 最后编辑:Alexandra Turner 更新时间:11/18/2023 访问量:106

问:

我的函数返回一个排序的数组,但它不是正确的数组:一些元素被复制,一些其他元素被删除。 例如,以下项的预期返回值为: 我得到这个:[93,13,73,30,79,31,95,22,26,1][1,13,22,26,30,31,73,79,93,95][1,1,22,26,26,26,30,30,95,95]

编辑:感谢您的回答,我已经更正了您在代码中显示的错误。 但它仍然不起作用。我已经完成了测试函数的帮助请求 我更改了变量的名称,使它们更易于理解。

这是我的代码:

我的通用 qsort 实现

分区函数,宽度:以字节为单位的值的大小(1 字节 = 8 位) void*T : 基数 left : 左索引, 右 : 右索引 compareFunction : 排序顺序函数

int partition_g(size_t width, void *T, int left, int right,
               int (*compareFunction)(const void *, const void *)) {

    uint8_t *Tbyte = T;
    //uniform draw in set [d,...,f]
    uint32_t swap_index = (rand() % (right - left + 1)) + left;

    //We swap T[right] and T[swap_index]

    uint8_t *y = malloc(width);
    if(y==NULL)exit(-1);
    // y <-- T[swap_index]
    memcpy(y, (Tbyte + swap_index * width), width);
    // T[swap_index] <-- T[left]
    memcpy((Tbyte + swap_index * width), (Tbyte + right * width), width);
    // T[left] <-- T[swap_index]
    memcpy((Tbyte + right * width), (Tbyte + swap_index * width), width);

    uint8_t *x = malloc(width);
    if(x==NULL)exit(-1);
    // x <-- T[right]
    memcpy(x,Tbyte + right * width, width);

    int n = right;
    for (int i = right - 1; i >= left; i--) {
        //compare (T[i],x)
        if (compareFunction((Tbyte + i * width), x)>0)
        {
            //T[n] <-- T[i]
            memcpy((Tbyte + n * width), (Tbyte + i * width), width);
            //T[i] <-- T[n-1]
            memcpy((Tbyte + i * width), (Tbyte + (n-1) * width), width);
            n--;
        }
    }
    //T[n] <-- x
    memcpy((Tbyte + n * width), x, width);

    //free of allocate variable
    free(y);
    free(x);

    return n;
}

递归调用 partion 函数的函数

void recqsortg(void *array, size_t elementSize, 
                int (*compareFunction)(const void *, const void *),int left, int right) {
    if (right > left) {
        int n = partition_g(elementSize, array, left, right, compareFunction);

        recqsortg(array, elementSize, compareFunction, left, n - 1);
        recqsortg(array, elementSize, compareFunction, n + 1, right);
    }
}

主要功能

void qsortg(void *array, size_t elementCount, size_t elementSize,
            int (*compareFunction)(const void *, const void *)) {
    recqsortg(array, elementSize, compareFunction, 0, elementCount - 1);
}

为我的测试功能制作的函数:


int a_strictSup_b_uint32(const void* a, const void* b) {
    return (*(uint32_t*)a > *(uint32_t*)b);
}

//function to display an array of integers
void printTab_entier_g(size_t nbelem, size_t width, void * T){
    uint64_t indice_depart;
    uint64_t res;
    uint8_t un_octet;
    uint8_t * Toctet = T;

    printf("[");

    for (int i = 0; i<nbelem; i++){
        res = 0;
        indice_depart = i * width;

        // on définit la valeur de res en parcourant width octets à partir de l'indice i
        for(int j = 0; j<width; j++){
            un_octet = *(Toctet + indice_depart + j);
            res = res + ((uint64_t)un_octet << j*8);
        }
        printf("%lu",res);
        if(i<nbelem-1)printf(",");
    }
    printf("]\n");
}

//function for assigning an element to an array
void affectationg_tab_g(void* T, uint32_t indice, uint64_t number, size_t width){
    
    uint8_t * Tprime = T;
    uint64_t depart_affectation = width * indice;
    
    for(uint64_t i = 0; i < width; i++){    //Attention l'entier number est tronqué si il > width
        *(Tprime + depart_affectation + i) = (number >> i*8) & 0xFF;
    }

}

//function that initializes an array of random elements in the set [0,...,99].
void init_random_tab_g(size_t Tlen, size_t width, void * T){
    uint32_t rd_number;
    for(int i = 0; i<Tlen; i++){
        rd_number = rand()%100;
        affectationg_tab_g(T,i,rd_number,width);
    }
}

我的测试函数

void test6()
{
    size_t Tlen = 10;
    uint32_t * T = malloc(Tlen*sizeof(uint32_t));
    uint32_t * T2 = malloc(Tlen*sizeof(uint32_t));
    init_random_tab_g(Tlen,sizeof(uint32_t),T);
    memcpy(T2,T,Tlen*sizeof(uint32_t));

    printf("input array :\n");
    printTab_entier_g(Tlen,sizeof(uint32_t),T);

    qsortg(T,Tlen,sizeof(uint32_t),a_strictSup_b_uint32);
    qsort(T2,Tlen,sizeof(uint32_t),a_strictSup_b_uint32);
    printf("sorted by (my qsort)qsortg :\n");
    printTab_entier_g(Tlen,sizeof(uint32_t),T);
    printf("Sorted by qsort :\n");
    printTab_entier_g(Tlen,sizeof(uint32_t),T2);


    free(T);
    free(T2);
}
int main(){
    //the way I initialize random
    srand(/*time(NULL)*/123);
    //how I call test6
    test6();
    return 0;
}

所有这些代码的输出是:

输入数组: [93,13,73,30,79,31,95,22,26,1]

排序方式 (my qsort)qsortg : [1,1,22,26,26,26,30,30,95,95]

按qsort排序: [1,13,22,26,30,31,73,79,93,95]

我们可以看到我的 qsortg 函数是假的

C 泛型快速 排序

评论

1赞 Eric Postpischil 11/17/2023
编辑问题以提供最小的可重现示例
2赞 Eric Postpischil 11/17/2023
rand()%(d-f-1))+d是错误的。
1赞 John Bollinger 11/17/2023
为什么你的分区函数需要 和 ?将相同的数据复制到它们中,并且在释放它们之前不要修改它们的内容。它们似乎完全是多余的。xy
1赞 John Bollinger 11/17/2023
我敦促您为变量使用更有意义的名称。除此之外,这样做将使代码的意图更易于理解,从而帮助您更轻松地发现问题。
2赞 Weather Vane 11/17/2023
你似乎把布尔值当成布尔值。以与 和 相同的方式使用其返回值。compareFunction()qsortstrcmp()memcmp()

答:

2赞 John Bollinger 11/17/2023 #1

您没有显示您在测试中使用的比较函数,并且问题没有记录比较函数的预期行为。此类函数的通常约定是标准库函数的约定,根据第一个参数是小于、等于还是大于第二个参数,它期望比较函数的返回值小于 0、等于零或大于零。qsort()

如果这也是您的期望,那么您的函数错误地使用了比较函数。使用传统的比较功能,这...partitiong()

        if (compareFunction((Toctet + i * width), x))

...询问元素是否不等于枢轴值,但你真正想问的是它是否大于枢轴值。那就是:i

        if (compareFunction((Toctet + i * width), x) > 0)

此外,您的随机枢轴选择公式是有问题的。考虑:

    uint32_t indice_swap = (rand() % (d - f - 1)) + d;

d是子数组下限的索引,也是上限的索引。那么,你应该预料到这将是负面的。在 C 中,运算符返回其操作数的代数商,任何小数部分都被截断。除其他外,这意味着当操作数具有相反的符号时,结果是负数,这通常就是这种情况,因为 的返回值是非负的。因此,您选择的枢轴位于您尝试排序的子数组之外,并且可能完全位于输入数组之外。相反,您需要以下信息:fd - f - 1%rand()

    uint32_t indice_swap = (rand() % (f - d + 1)) + d;

添加:

此外,您错误地实现了最右边元素与枢轴元素的交换。考虑:

    // T[swap_index] <-- T[left]
    memcpy((Tbyte + swap_index * width), (Tbyte + right * width), width);
    // T[left] <-- T[swap_index]
    memcpy((Tbyte + right * width), (Tbyte + swap_index * width), width);

代码注释混淆了“左”和“右”,但即便如此,它们也给出了关于正在发生的事情的正确想法。透视值被覆盖,然后将相同的值复制回原始位置,而不会产生任何净效应。看来你的意图是后者

    // T[right] <-- y
    memcpy((Tbyte + right * width), y, width);

在实践中,您需要最后一个副本的唯一原因是因为您稍后会从结果中读取。如果你改为阅读,或者你只是摆脱并使用,那么那不是问题。这就是为什么我在这个答案的初始版本中忽略了这个问题。xxyxy


通过这三项更改,我能够将传统样式的比较函数与您的代码一起使用,以获得示例输入数组的正确排序。

评论

0赞 Alexandra Turner 11/17/2023
感谢您抽出宝贵时间回复。你的答案非常完整和清晰。我已经根据你告诉我的内容更正了我的代码。但它仍然无法正常工作。你能帮帮我吗?(我已经通过添加测试完成了我的请求。
0赞 John Bollinger 11/18/2023
@AlexandraTurner,我已经更新了这个答案,以解决你的代码中的另一个问题。
0赞 Alexandra Turner 11/18/2023
它终于起作用了,这是我第一次遇到这么大的错误,我意识到这只是一个愚蠢的错误。非常感谢您的帮助、清晰的回答和耐心等待。祝你有美好的一天/周末或类似的事情。很多