c - c中的霍尔快速排序

Question

与我正在使用的其他用户类似this维基百科算法。不过，我尝试使用指针算术重新实现该算法。但是我很难找到哪里出了问题。

我认为这个 if 语句可能是原因，但我不确定。

...  
if (left >= right) {  
ret = (right - ptr);  
return ret;  
}  
temp = *left;
*left = *right;
*right = temp;

/* sortstuff.h */

extern void quicksort(const size_t n, int * ptr);

/* sortstuff.c */ 
size_t quicksortpartition(const size_t n, int * ptr);

void quicksort(const size_t n, int * ptr) {
    int* end = ptr + n - 1;

    // for debug purposes
    if (original_ptr == NULL) {
        original_ptr = ptr;
        original_count = n;
    }

    if (n > 1) {
        size_t index = quicksortpartition(n, ptr);
        quicksort(index, ptr);
        quicksort(n - index - 1, ptr + index + 1);
    }
    return;
}

size_t quicksortpartition(const size_t n, int * ptr) {
    int* right = ptr + n - 1;
    int* pivot = ptr + (n - 1) / 2;
    int* left = ptr;
    int temp;
    size_t ret = NULL;

    while (1) {
        while (*left <= *pivot && left < pivot) {
            ++left;
        }
        while (*right > *pivot) {
            --right;
        }
        if (left >= right) {
            ret = (right - ptr);
            return ret;
        }
        temp = *left;
        *left = *right;
        *right = temp;
        //print_arr();
    }
}

int main(void) {

}

/* main.c */ 

int array0[] = {5, 22, 16, 3, 1, 14, 9, 5};
const size_t array0_count = sizeof(array0) / sizeof(array0[0]);

int main(void) {
    quicksort(array0_count, array0);

    printf("array out: ");
    for (size_t i = 0; i != array0_count; ++i) {
        printf("%d ", array0[i]);
    }
    puts("");
}

我认为没有任何差错

Answer 1

您提供的代码未准确实现您引用的算法。特别考虑这个循环:

        while (*left <= *pivot && left < pivot) {
            ++left;
        }

算法描述中的相应循环没有 left < pivot 的类似物循环退出标准，及其类似 *left <= *pivot使用严格小于( < )，而不是( <= )。

很容易看出，前一个差异必定构成实现错误。枢轴的最终排序位置是左指针和右指针相遇的位置，但该条件阻止左指针前进超过枢轴的初始位置。因此，如果正确的位置是初始位置的右侧，那么配分函数肯定无法返回正确的值。需要更深入的分析才能认识到，事实上，在这种情况下，分区函数还容易无限循环，尽管我认为这在某种程度上依赖于数据。

后一个差异构成临时错误。如果所选的主元值恰好是数组中的最大值，则存在溢出数组末尾的风险，但这部分基于以下事实: left < pivot条件是错误的，必须删除。您可以将后者替换为 left < right来解决这个问题，但是尽管您可以通过这种方式形成一个工作类别，但它可能不会改进算法描述中呈现的逻辑细节。

但请注意，使用 <=变化，要么 quicksortpartition()需要做额外的工作(目前未提供)以确保枢轴值最终位于计算的枢轴位置，否则 quicksort函数需要放弃这种情况将会发生的假设。前者更实用，假设您希望您的排序是健壮的。