我试图计算在C中我的快速排序中发生的交换次数。但是，我得到的值不正确，并且不确定我哪里出错了。我正在使用结构作为要排序的数组。
struct anArray{
int numbers[maxSize];
int swaps;
};
/* Partition function */
int partition(struct anArray *array, int start, int end){
if(start == end){
return start;
}
int pivot = array->numbers[end];
int low = start - 1;
int high = end;
for(;;){
do{
low++;
} while(array->numbers[low] < pivot);
do{
high--;
} while(array->numbers[high] > pivot);
/* Detector for when the cells meet */
if(low >= high){
swap(array, low, end);
return low;
}
}
/* Swapping the values */
swap(array, low, high);
}
这是我的分区函数，用于“分离”数组。
void quickSort(struct anArray *array, int start, int end){
if(end - start <= 0){ return; }
else{
int pivot = array->numbers[end];
int partitionPoint = partition(array, start, end);
quickSort(array, start, partitionPoint - 1);
quickSort(array, partitionPoint + 1, end);
}
}
这是我的快速排序功能。这是一个递归函数。我的交换函数每次调用时都会将计数器增加1。
在我的主程序中，我设置了myArray-> swaps = counter; 但是交换发生的次数是不正确的。例如，如果我对从1到9的数组进行排序，那么交换次数应该为0，但得到9。我尝试仅在分区函数中使用递增计数器，但结果却相同。
我的分区功能有问题吗？
非常感谢你
编辑1：
这是我的交换函数。
void swap(struct anArray *array, int first, int second){
int temp = array->numbers[first];
array->numbers[first] = array->numbers[second];
array->numbers[second] = temp;
counter++;
}
我试过使用
void swap(struct anArray *array, int first, int second, int swapCount)
然后在调用交换函数时将swapCount设置为array-> swaps，并将其递增1，但这给了我相同的答案。
这是我主要的一部分。
int main(){
struct anArray *ascending = (struct anArray*)malloc(10 * sizeof(struct anArray));
int ascend[maxSize] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
initArray(ascending, ascend);
quickSort(ascending, 0, maxSize - 1);
ascending->swaps = counter;
printf("Test: Unique random values\nSorted: [ ");
for(int i = 0; i < maxSize; i++){
printf("%i ", ascending->numbers[i]);
}
printf("]\nSwaps: %i\nComps: \n\n", ascending->swaps);
我主体的其他部分只是要排序的其他数组。initArray用于设置array-> numbers的值，并将array-> swaps重置为0。
您的quicksort代码似乎很好。我没有严格检查它，但是它通过了一个简单的测试，所以我没有做进一步的研究。（编辑：根据您的反馈，我在第二次更新中创建了第三个版本，该版本表明排序存在较大数据输入问题）。
主要错误是malloc的顶部main。我们不想要struct的数组anArray：
struct anArray *ascending = malloc(10 * sizeof(struct anArray));
也就是说，我们不希望（例如）10层结构，我们希望有一个单一的结构，并填写10个ints表示进入numbers是在这一领域单一结构。
该initArray函数未发布，因此我不得不猜测/推断出它可能是什么。基于上述错误，我不确定该numbers初始化是否正确。
从发布的代码片段中，我可以将整个程序组合在一起。我创建了两个版本：
其中一个带有注释的错误（但不固定），可以干净地进行编译。
而且，可以对所有数组大小进行完全清理，工作和通用化的一秒钟[请原谅免费的样式清理]
这是您的原始代码中（接近的地方），其中的错误已注释：
#include <stdio.h>
#include <stdlib.h>
// NOTE/BUG: this was not defined and _fixed_ defines should be all caps
#define maxSize 10
struct anArray {
int numbers[maxSize];
int swaps;
};
int counter;
void
initArray(struct anArray *array,const int *src)
{
for (int idx = 0; idx < maxSize; ++idx)
array->numbers[idx] = src[idx];
array->swaps = 0;
}
void
swap(struct anArray *array, int first, int second)
{
int temp = array->numbers[first];
array->numbers[first] = array->numbers[second];
array->numbers[second] = temp;
counter++;
}
/* Partition function */
int
partition(struct anArray *array, int start, int end)
{
if (start == end) {
return start;
}
int pivot = array->numbers[end];
int low = start - 1;
int high = end;
for (;;) {
do {
low++;
} while (array->numbers[low] < pivot);
do {
high--;
} while (array->numbers[high] > pivot);
/* Detector for when the cells meet */
if (low >= high) {
swap(array, low, end);
return low;
}
}
/* Swapping the values */
swap(array, low, high);
}
void
quickSort(struct anArray *array, int start, int end)
{
if (end - start <= 0) {
return;
}
else {
// NOTE/BUG: pivot is _not_ used
int pivot = array->numbers[end];
int partitionPoint = partition(array, start, end);
quickSort(array, start, partitionPoint - 1);
quickSort(array, partitionPoint + 1, end);
}
}
int
main(void)
{
// NOTE/BUG: we do _not_ want an array of the struct, but an array of int
// that is allocated for "number" _inside_ the struct
struct anArray *ascending = malloc(10 * sizeof(struct anArray));
int ascend[maxSize] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// NOTE/BUG: this was not defined
initArray(ascending, ascend);
quickSort(ascending, 0, maxSize - 1);
ascending->swaps = counter;
printf("Test: Unique random values\nSorted: [ ");
for (int i = 0; i < maxSize; i++) {
printf("%i ", ascending->numbers[i]);
}
printf("]\nSwaps: %i\nComps: \n\n", ascending->swaps);
return 0;
}
这是一个清理工作的版本。我已经对其进行了概括，因此它可以采用任意长的数组。我还做了一些样式和代码清除：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *numbers;
int size;
int swaps;
} Array;
Array *
initArray(const int *src,int size)
{
Array *array = malloc(sizeof(Array));
array->numbers = malloc(size * sizeof(int));
array->size = size;
// store in reverse order so the sort will actually do something
for (int idx = 0; idx < size; ++idx)
array->numbers[size - 1 - idx] = src[idx];
array->swaps = 0;
return array;
}
void
freeArray(Array *array)
{
free(array->numbers);
free(array);
}
void
swap(Array *array, int first, int second)
{
int temp = array->numbers[first];
array->numbers[first] = array->numbers[second];
array->numbers[second] = temp;
array->swaps += 1;
}
/* Partition function */
int
partition(Array *array, int start, int end)
{
if (start == end)
return start;
int pivot = array->numbers[end];
int low = start - 1;
int high = end;
for (;;) {
do {
low++;
} while (array->numbers[low] < pivot);
do {
high--;
} while (array->numbers[high] > pivot);
/* Detector for when the cells meet */
if (low >= high) {
swap(array, low, end);
return low;
}
}
/* Swapping the values */
swap(array, low, high);
}
void
quickSort(Array *array, int start, int end)
{
if (end - start <= 0)
return;
//int pivot = array->numbers[end];
int partitionPoint = partition(array, start, end);
quickSort(array, start, partitionPoint - 1);
quickSort(array, partitionPoint + 1, end);
}
int
main(void)
{
// NOTE/BUG: we do _not_ want an array of the struct, but an array of int
// that is allocated for "number" _inside_ the struct
int original[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int size = sizeof(original) / sizeof(original[0]);
Array *ascending = initArray(original, size);
quickSort(ascending, 0, ascending->size - 1);
printf("Test: Unique random values\nSorted: [ ");
for (int i = 0; i < ascending->size; i++) {
int expected = original[i];
int actual = ascending->numbers[i];
printf("%d%s ", actual, (actual == expected) ? "" : "???");
}
printf("]\nSwaps: %i\nComps: \n\n", ascending->swaps);
freeArray(ascending);
return 0;
}
更新：
这条线
int size = sizeof(original) / sizeof(original[0]);到底是做什么的？它是否为我提供了一个整数，我将其设置为数组中可以容纳多少个数字的大小？
是的，这是获取固定大小数组的元素数量计数的常见/惯用技巧：
int array[] = { 1, 2, 3 };
size_t count = sizeof(array) / sizeof(array[0]);
在这里，sizeof(array)是单个元素的大小的3倍[以字节为单位] [为int，即4个字节]，所以我们有3 * 4或12。
sizeof(array[0])是数组的单个第一个元素的大小，再次为an int，因此为4。
因此，当我们将两者相除时，我们得到的12 / 4值为3或3。
如果是这样的话，如果sizeof（original [0]）恰好很大，我可以容纳的数字量会不会真的很少？
不，因为分裂。不管元素的大小（以字节为单位）有多大，因为比率总是产生元素的数量。
sizeof(arr) / sizeof(arr[0])当我们这样做时，该技巧将有助于获得计数：int arr[] = { ... };
如果我们这样做：
#define ARRCOUNT 3
int arr[ARRCOUNT] = { 1, 2, 3 };
我们已经知道计数了（即是ARRCOUNT）。
该sizeof/sizeof技巧的[轻微]优势在于，如果我们错误地将错误定义ARRCOUNT为4，它仍会编译，链接和运行，但会产生不正确的结果[因为只有3个元素]。
这是一个足够常见的技巧，我们可以定义一个通用宏[我们可以通过将其放入文件来重复使用.h]：
#define ARRAY_COUNT(arr_) (sizeof(arr_) / sizeof(arr_))
更新＃2：
我已经尝试过您的代码（甚至尝试过复制和粘贴），但是尽管要排序的数组只是从{1到10}，但是我的交换仍然显示9。不知道为什么这种情况持续发生。
我相信[现在]您本身就有一个错误。
我制作了另一个版本，该版本具有更广泛的测试数据生成和比较功能。
至少由于测试的结构方式，已排序数组的第一个元素应始终具有值1。
失败的测试是对原始数组进行随机混洗，然后再将其发送进行排序的测试。
您可以根据需要添加其他测试。数组不必太大就可以显示问题。例如，以下单个测试足以产生错误：
bigtest(100,237,1);
无论如何，这是增强的诊断代码：
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 60
typedef struct {
int *numbers;
int size;
int swaps;
} Array;
Array *
initArray(const int *src,int size,int randshuf)
{
int idx;
Array *array = malloc(sizeof(Array));
array->numbers = malloc(size * sizeof(int));
array->size = size;
array->swaps = 0;
// store in reverse order so the sort will actually do something
switch (randshuf) {
case 0: // reverse the numbers
for (idx = 0; idx < size; ++idx)
array->numbers[size - 1 - idx] = src[idx];
break;
default: // do _crude_ random shuffle
for (idx = 0; idx < size; ++idx)
array->numbers[idx] = 0;
for (idx = 0; idx < size; ++idx) {
while (1) {
int ridx = rand() % size;
if (array->numbers[ridx] == 0) {
array->numbers[ridx] = src[idx];
break;
}
}
}
break;
}
return array;
}
void
freeArray(Array *array)
{
free(array->numbers);
free(array);
}
void
swap(Array *array, int first, int second)
{
int temp = array->numbers[first];
array->numbers[first] = array->numbers[second];
array->numbers[second] = temp;
array->swaps += 1;
}
/* Partition function */
int
partition(Array *array, int start, int end)
{
if (start == end)
return start;
int pivot = array->numbers[end];
int low = start - 1;
int high = end;
for (;;) {
do {
low++;
} while (array->numbers[low] < pivot);
do {
high--;
} while (array->numbers[high] > pivot);
/* Detector for when the cells meet */
if (low >= high) {
swap(array, low, end);
return low;
}
}
/* Swapping the values */
swap(array, low, high);
}
void
quickSort(Array *array, int start, int end)
{
if (end - start <= 0)
return;
//int pivot = array->numbers[end];
int partitionPoint = partition(array, start, end);
quickSort(array, start, partitionPoint - 1);
quickSort(array, partitionPoint + 1, end);
}
void
print_orig(const int *orig,int count)
{
int len = 0;
printf("Test: Original numbers (%d):\n",count);
for (int idx = 0; idx < count; ++idx) {
len += printf(" %10d ", orig[idx]);
if (len >= MAXLEN) {
printf("\n");
len = 0;
}
}
if (len > 0)
printf("\n");
}
int
print_array(Array *array,const int *orig,const char *reason)
{
int len = 0;
int cmp;
int err = -1;
printf("Test: Array Values (%s):\n",reason);
for (int idx = 0; idx < array->size; ++idx) {
int actual = array->numbers[idx];
if (orig != NULL) {
int expected = orig[idx];
cmp = (actual == expected);
}
else
cmp = 1;
len += printf(" %10d%c", actual, cmp ? ' ' : '?');
if (len >= MAXLEN) {
printf("\n");
len = 0;
}
if (cmp)
continue;
if (err < 0)
err = idx;
}
if (orig != NULL)
printf("\nSwaps: %i\nComps: \n\n", array->swaps);
else {
if (len > 0)
printf("\n");
}
return err;
}
void
bigtest(int count,int randgap,int randshuf)
// count -- number of elements (negative means random)
// randgap -- gap between element values (negative means random)
// randshuf -- 0=simple reverse, 1=random shuffle
{
int *orig;
Array *array;
printf("\n");
for (int idx = 1; idx <= 80; ++idx)
printf("-");
printf("\n");
printf("COUNT: %d, RANDGAP: %d, RANDSHUF: %d\n",count,randgap,randshuf);
// get number of elements
if (count < 0)
count = (rand() % count) + 1;
// get element gap (e.g. 1 --> {1, 2, 3}, 2 --> { 1, 3, 5 }
if (randgap < 0)
randgap = (rand() % randgap) + 1;
printf("COUNT: %d, RANDGAP: %d, RANDSHUF: %d\n",count,randgap,randshuf);
// get original array
orig = malloc(sizeof(int) * count);
// fill in original array
do {
int val = 1;
// simple gap
if (randgap >= 0) {
if (randgap == 0)
randgap = 1;
for (int idx = 0; idx < count; ++idx, val += randgap)
orig[idx] = val;
break;
}
// random gap
int gap;
for (int idx = 0; idx < count; ++idx, val += gap) {
orig[idx] = val;
gap = (rand() % randgap) + 1;
}
} while (0);
print_orig(orig,count);
array = initArray(orig,count,randshuf);
print_array(array,NULL,"Shuffled");
quickSort(array, 0, array->size - 1);
print_array(array,orig,"Sorted");
freeArray(array);
free(orig);
}
int
main(void)
{
bigtest(10,0,0);
bigtest(-100,23,0);
bigtest(-1000,-2337,0);
bigtest(-1000,-2337,1);
return 0;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句