提问人:Alexandra Turner 提问时间:11/17/2023 最后编辑:Alexandra Turner 更新时间:11/18/2023 访问量:106
我正在尝试在 C 中将 qsort algortihm 实现为通用函数
I am trying to implement qsort algortihm as a generic function in C
问:
我的函数返回一个排序的数组,但它不是正确的数组:一些元素被复制,一些其他元素被删除。
例如,以下项的预期返回值为: 我得到这个:[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 函数是假的
答:
您没有显示您在测试中使用的比较函数,并且问题没有记录比较函数的预期行为。此类函数的通常约定是标准库函数的约定,根据第一个参数是小于、等于还是大于第二个参数,它期望比较函数的返回值小于 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 中,运算符返回其操作数的代数商,任何小数部分都被截断。除其他外,这意味着当操作数具有相反的符号时,结果是负数,这通常就是这种情况,因为 的返回值是非负的。因此,您选择的枢轴位于您尝试排序的子数组之外,并且可能完全位于输入数组之外。相反,您需要以下信息:f
d - 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);
在实践中,您需要最后一个副本的唯一原因是因为您稍后会从结果中读取。如果你改为阅读,或者你只是摆脱并使用,那么那不是问题。这就是为什么我在这个答案的初始版本中忽略了这个问题。x
x
y
x
y
通过这三项更改,我能够将传统样式的比较函数与您的代码一起使用,以获得示例输入数组的正确排序。
评论
rand()%(d-f-1))+d
是错误的。x
y
compareFunction()
qsort
strcmp()
memcmp()