c - 快速排序算法不适用于所有数组

Question

这是一项家庭作业。我最终会将这段代码翻译成 MIPS 汇编，但这对我来说是容易的部分。我已经调试这个代码好几个小时了，并且去过我的教授的办公时间，但我仍然无法使我的快速排序算法工作。以下是代码以及我对问题所在的一些评论:

// This struct is in my .h file
typedef struct {
    // v0 points to the first element in the array equal to the pivot
    int *v0;

    // v1 points to the first element in the array greater than the pivot (one past the end of the pivot sub-array)
    int *v1;
} PartRet;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

PartRet partition(int *lo, int *hi) {
    // Will later be translating this to MIPS where 2 values can be returned. I am using a PartRet struct to simulate this.
    PartRet retval;

    // We must use the last item as the pivot
    int pivot = *hi;

    int *left = lo;

    // Take the last value before the pivot
    int *right = hi - 1;

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

        while((right > lo) && (*right > pivot)) {
            --right;
        }

        if (left < right) {
            swap(left++, right--);
        }
    }

    // Is this correct? left will always be >= right after the while loop
    if (*hi < *left) {
        swap(left, hi);
    }

    // MADE CHANGE HERE
    int *v0 = hi;
    int *v1;

    // Starting at the left pointer, find the beginning of the sub-array where the elements are equal to the pivot
    // MADE CHANGE HERE
    while (v0 > lo && *(v0 - 1) >= pivot) {
        --v0;
    }

    v1 = v0;

    // Starting at the beginning of the sub-array where the elements are equal to the pivot, find the element after the end of this array.
    while (v1 < hi && *v1 == pivot) {
    ++v1;
    }

    if (v1 <= v0) {
        v1 = hi + 1;
    }

    // Simulating returning two values
    retval.v0 = v0;
    retval.v1 = v1;

    return retval;
}

void quicksort(int *array, int length) {
    if (length < 2) {
        return;
    }

    PartRet part = partition(array, array + length - 1);

    // I *think* this first call is correct, but I'm not sure.
    int firstHalfLength = (int)(part.v0 - array);
    quicksort(array, firstHalfLength);

    int *onePastEnd = array + length;
    int secondHalfLength = (int)(onePastEnd - part.v1);

    // I have a feeling that this isn't correct
    quicksort(part.v1, secondHalfLength);
}

我什至尝试使用在线代码示例重写代码，但要求是使用 lo 和 hi 指针，但我发现没有代码示例使用它。当我调试代码时，我最终只会使代码适用于某些数组，而不是其他数组，特别是当枢轴是数组中最小的元素时。

Answer 1

分区代码存在问题。以下是来自下面 SSCCE 代码的 4 个简单测试输出:

array1:
Array (Before):
[6]: 23 9 37 4 2 12
Array (First half partition):
[3]: 2 9 4
Array (First half partition):
[1]: 2
Array (Second half partition):
[1]: 9
Array (Second half partition):
[2]: 23 37
Array (First half partition):
[0]:
Array (Second half partition):
[1]: 23
Array (After):
[6]: 2 4 9 12 37 23


array2:
Array (Before):
[3]: 23 9 37
Array (First half partition):
[1]: 23
Array (Second half partition):
[1]: 9
Array (After):
[3]: 23 37 9


array3:
Array (Before):
[2]: 23 9
Array (First half partition):
[0]:
Array (Second half partition):
[1]: 23
Array (After):
[2]: 9 23


array4:
Array (Before):
[2]: 9 24
Array (First half partition):
[0]:
Array (Second half partition):
[1]: 9
Array (After):
[2]: 24 9

SSCCE 代码

#include <stdio.h>

typedef struct
{
    int *v0;    // v0 points to the first element in the array equal to the pivot
    int *v1;    // v1 points to the first element in the array greater than the pivot (one past the end of the pivot sub-array)
} PartRet;

static void dump_array(FILE *fp, const char *tag, int *array, int size)
{
    fprintf(fp, "Array (%s):\n", tag);
    fprintf(fp, "[%d]:", size);
    for (int i = 0; i < size; i++)
        fprintf(fp, " %d", array[i]);
    putchar('\n');
}

static void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

static PartRet partition(int *lo, int *hi)
{
    // Will later be translating this to MIPS where 2 values can be
    // returned.  I am using a PartRet struct to simulate this.
    PartRet retval;

    // This code probably won't ever be hit as the base case in the QS
    // function will return first
    if ((hi - lo) < 1)
    {
        retval.v0 = lo;
        retval.v1 = lo + (hi - lo) - 1;
        return retval;
    }

    // We must use the last item as the pivot
    int pivot = *hi;

    int *left = lo;

    // Take the last value before the pivot
    int *right = hi - 1;

    while (left < right)
    {
        if (*left <= pivot)
        {
            ++left;
            continue;
        }

        if (*right >= pivot)
        {
            --right;
            continue;
        }

        swap(left, right);
    }

    // Is this correct? left will always be >= right after the while loop
    swap(left, hi);

    int *v0 = left;
    int *v1;

    // Starting at the left pointer, find the beginning of the sub-array
    // where the elements are equal to the pivot
    while (v0 > lo && *(v0 - 1) == pivot)
    {
        --v0;
    }

    v1 = v0;

    // Starting at the beginning of the sub-array where the elements are
    // equal to the pivot, find the element after the end of this array.
    while (v1 < hi && *v1 == pivot)
    {
        ++v1;
    }

    // Simulating returning two values
    retval.v0 = v0;
    retval.v1 = v1;

    return retval;
}

static void quicksort(int *array, int length)
{
    if (length < 2)
    {
        return;
    }

    PartRet part = partition(array, array + length - 1);

    // I *think* this first call is correct, but I'm not sure.
    int firstHalfLength = (int)(part.v0 - array);
    dump_array(stdout, "First half partition", array, firstHalfLength);
    quicksort(array, firstHalfLength);

    int *onePastEnd = array + length;
    int secondHalfLength = (int)(onePastEnd - part.v1);

    // I have a feeling that this isn't correct
    dump_array(stdout, "Second half partition", part.v1, secondHalfLength);
    quicksort(part.v1, secondHalfLength);
}

static void mini_test(FILE *fp, const char *name, int *array, int size)
{
    putc('\n', fp);
    fprintf(fp, "%s:\n", name);
    dump_array(fp, "Before", array, size);
    quicksort(array, size);
    dump_array(fp, "After", array, size);
    putc('\n', fp);
}

int main(void)
{
    int array1[] = { 23, 9, 37, 4, 2, 12 };
    enum { NUM_ARRAY1 = sizeof(array1) / sizeof(array1[0]) };
    mini_test(stdout, "array1", array1, NUM_ARRAY1);

    int array2[] = { 23, 9, 37, };
    enum { NUM_ARRAY2 = sizeof(array2) / sizeof(array2[0]) };
    mini_test(stdout, "array2", array2, NUM_ARRAY2);

    int array3[] = { 23, 9, };
    enum { NUM_ARRAY3 = sizeof(array3) / sizeof(array3[0]) };
    mini_test(stdout, "array3", array3, NUM_ARRAY3);

    int array4[] = { 9, 24, };
    enum { NUM_ARRAY4 = sizeof(array4) / sizeof(array4[0]) };
    mini_test(stdout, "array4", array4, NUM_ARRAY4);

    return(0);
}

我没有对排序代码进行任何算法更改。我只是添加了 dump_array() 函数，并对它进行了策略调用，并添加了 mini_test() 函数和 main()。这些类型的装置非常有帮助。请注意，当输入数组的大小为 2 并且顺序错误时，分区是正确的，但当大小为 2 并且顺序正确时，分区会反转数组元素的位置。这是有问题的!解决了这个问题，剩下的大部分问题就可以解决了。尝试使用所有 6 种排列(3 个不同值)中的 3 个元素数组；考虑使用 3 个元素和仅 2 个不同的值，以及 3 个元素和仅 1 个值。