c - C中的快速排序实现

Question

目标:我正在尝试在 C 中实现快速排序。
问题:这个 C 的快速排序实现进入无限循环。我认为分区函数没问题，因为使用测试用例，枢轴(设置为索引 0)总是移动到正确的位置。我不明白为什么快速排序函数最终不会达到基本情况。

这个实现可能有什么问题？

# include <stdio.h>

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

// Partitioning algorithm
int partition(int *L, int left, int right){
    int pivot = L[0];

    while (right > left) {
            while (L[left] < pivot) {
                    left = left + 1;
            }
            while (L[right] > pivot) {
                    right = right - 1;
            }
            swap(&L[left], &L[right]);
    }
    swap(&pivot, &L[left]);
    return left;
}

// Quicksort recursion
void quicksort(int *L, int start, int end) {
    if (start >= end) {
            return;
    }
    else {
            int splitPoint = partition(L, start, end);
            quicksort(L, start, splitPoint-1);
            quicksort(L, splitPoint+1, end);
    }
}

int main() {
    int myList[] = {12, 43, -16, 0, 2, 5, 1, 13, 2, 2, -1};
    printf("UNSORTED LIST\n");
    int *pointer = myList;
    for (int i = 0; i < 10; i++) {
            printf("%d ", *(pointer+i));
    }
    quicksort(myList, 0, 9);
    printf("\nSORTED LIST\n");
    for (int i = 0; i < 10; i++) {
            printf("%d ", *(pointer+i));
    }
    printf("\n");
}

Answer 1

初始枢轴选择应该是 L[left] 而不是 L[0]，不是吗？然而，这并不是分区函数中的唯一问题。

此代码有效:

#include <stdio.h>

// Swapping algorithm
static inline
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

static void dump_list(const char *tag, int *ptr, int left, int right)
{
    printf("%15s [%d..%d]: ", tag, left, right);
    for (int i = left; i <= right; i++)
        printf(" %3d", ptr[i]);
    putchar('\n');
}

// Partitioning algorithm
static
int partition(int *L, int left, int right)
{
    int pivot = left;
    int p_val = L[pivot];

    while (left < right)
    {
        while (L[left] <= p_val)
            left++;
        while (L[right] > p_val)
            right--;
        if (left < right)
            swap(&L[left], &L[right]);
    }
    swap(&L[pivot], &L[right]);
    return right;
}

// Quicksort recursion
static
void quicksort(int *L, int start, int end)
{
    if (start >= end)
        return;
    //dump_list("PRE-PARTITION", L, start, end);
    int splitPoint = partition(L, start, end);
    //dump_list("POST-PARTITION", L, start, end);
    //printf("Split point: %d\n", splitPoint);
    quicksort(L, start, splitPoint - 1);
    quicksort(L, splitPoint + 1, end);
}

int main(void)
{
    int myList[] = {12, 43, -16, 0, 2, 5, 1, 13, 2, 2, -1};
    dump_list("UNSORTED LIST", myList, 0, 9);
    quicksort(myList, 0, 9);
    dump_list("SORTED LIST", myList, 0, 9);
}

它产生输出:

  UNSORTED LIST [0..9]:   12  43 -16   0   2   5   1  13   2   2
    SORTED LIST [0..9]:  -16   0   1   2   2   2   5  12  13  43

启用调试打印后，输出为:

  UNSORTED LIST [0..9]:   12  43 -16   0   2   5   1  13   2   2
  PRE-PARTITION [0..9]:   12  43 -16   0   2   5   1  13   2   2
 POST-PARTITION [0..9]:    2   2 -16   0   2   5   1  12  13  43
Split point: 7
  PRE-PARTITION [0..6]:    2   2 -16   0   2   5   1
 POST-PARTITION [0..6]:    1   2 -16   0   2   2   5
Split point: 5
  PRE-PARTITION [0..4]:    1   2 -16   0   2
 POST-PARTITION [0..4]:  -16   0   1   2   2
Split point: 2
  PRE-PARTITION [0..1]:  -16   0
 POST-PARTITION [0..1]:  -16   0
Split point: 0
  PRE-PARTITION [3..4]:    2   2
 POST-PARTITION [3..4]:    2   2
Split point: 4
  PRE-PARTITION [8..9]:   13  43
 POST-PARTITION [8..9]:   13  43
Split point: 8
    SORTED LIST [0..9]:  -16   0   1   2   2   2   5  12  13  43