为什么这个 Shaker Sort 代码在 C 中不起作用

Question

我正在用 C 实现一个通用的 Shaker Sort 算法，各种网站以一种不断给我分段错误和其他错误的方式呈现代码，但它在使用其他语言时工作得很好。例如，this code 如果我将它保留在 C# 中没有问题，但在将其适应 C 后它停止工作。

这是我忠实改编上述代码的完整工作示例：

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// definition of a comparator interface needed by the sort function 
// to compare the values in the array passed as 'void *'
typedef int (*comparator)(void *, void *);

// implementation of the comparator interface for the int type
int int_comparator(void *a, void *b)
{
    int *aa = a;
    int *bb = b;
    return (*aa > *bb) - (*aa < *bb);
}

// generic swap, lacking error checking for the malloc call to keep things brief
void swap(void *a, void *b, size_t size)
{
    unsigned char *aa = a;
    unsigned char *bb = b;
    unsigned char *tmp = malloc(size);

    memcpy(tmp, aa, size);
    memcpy(aa, bb, size);
    memcpy(bb, tmp, size);
    free(tmp);
}

// takes the array, its length, the size of the type it contains, and a pointer 
// to a comparator function according to the type contained in the array
void shaker_sort(void *array, size_t length, size_t size, comparator cmp)
{
    // can't dereference a 'void *', so the array is 
    // now considered as a sequence of raw bytes
    unsigned char *arr = array;
    size_t start = 0;
    size_t end = length - 1;
    int swapped = 1;

    while (swapped) {
        swapped = 0;

        for (size_t i = start; i < end; i++) {
            // since we have a sequence of bytes, access to the original 
            // array elements happens by reading chunks of data of the
            // size of the type contained in the array
            if (cmp(&arr[i * size], &arr[i * size + size]) > 0) {
                swap(&arr[i * size], &arr[i * size + size], size);
                swapped = 1;
            }
        }

        if (!swapped) break;

        swapped = 0;
        end--;

        for (size_t i = end; i >= start; i--) {
            if (cmp(&arr[i * size], &arr[i * size + size]) > 0) {
                swap(&arr[i * size], &arr[i * size + size], size);
                swapped = 1;
            }
        }

        start++;
    }
}

int main(void)
{
    int arr[] = {3, 0, -4, 6, 1};
    size_t length = sizeof(arr) / sizeof(int);

    shaker_sort(arr, length, sizeof(int), int_comparator);

    for (size_t i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }

    puts("");
}

用gcc -Wall -Wextra -pedantic -std=c11 test.c -o test编译没问题，但随后会出现段错误。 valgrind --tool=memcheck --leak-check=full ./test 的快速运行表明我显然正在使用未初始化的值、执行无效读取和其他便利措施。为了简洁起见，我没有包括输出，但您可以复制整个代码并重现我的确切结果。

现在，奇怪的是，如果我像这样编写 Shaker Sort 的第二个 for 循环，代码将与干净的 valgrind 输出完美配合：

for (size_t i = end; i > start; i--) {
    if (cmp(&arr[i * size], &arr[i * size - size]) < 0) {
        swap(&arr[i * size], &arr[i * size - size], size);
        swapped = 1;
    }
}

基本上，循环现在停在位置 start + 1 的元素处，而不是像以前那样将当前元素与其后继元素进行比较，它将当前元素与其前导元素进行比较.就是这样，我一点也不知道为什么原始形式的代码在 C# 和可能 Java 和其他语言中很好，但在 C 中它需要这个小的调整。有人可以解释一下这个问题吗？

Answer 1

start 和 i 是无符号的，

    for (size_t i = end; i >= start; i--)

第一次来start是0次

我倒数到 0，然后从 0 中减去 1 得到一些其他值，该值无符号大于或等于零，循环继续

改为这样做：

    for (size_t i = end; i > start; i--) {
        if (cmp(&arr[i * size - size], &arr[i * size]) > 0) {
            swap(&arr[i * size - size ], &arr[i * size], size);
            swapped = 1;
        }

    }

为什么这个 Shaker Sort 代码在 C 中不起作用

Why this Shaker Sort code doesn't work in C

c

sorting

bubble-sort