c - 在 C 中实现快速排序的段错误

Question

我正在尝试执行 Reema Thareja 在 Data Structures Using C 一书中提到的快速排序代码。

问题是我无法将排序后的数组作为输出。相反，当我在数组中添加元素时，输出屏幕消失，再次运行代码时我得到以下信息:

我使用的是 Turbo C++ 版本:3.2 编译器

#include <stdio.h>
#include <conio.h>
void quicksort(int arr[],int l,int r);
void main()
{
    int arr[10],l,r,i,n;
    printf("Enter Array size: ");
    scanf("%d",&n);
    printf("Enter Elements: ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    quicksort(arr,0,n-1);
    printf("The Sorted Array is: ");
    for (i = 0; i < n; i++)
    {
        printf("%d",arr[i]);
    }
    getch();
}
int partition(int arr[],int l,int r)
{
    int left,right,temp,loc,flag;
    loc=left=l;
    right=r;
    flag=0;
    while(flag!=1)
    {
        while((arr[loc]<=arr[right]) && loc!=right)
        {
            right--;
        }
        if(loc==right)
        {
            flag=1;
        }
        else if(arr[loc]>arr[right])
        {
            temp=arr[loc];
            arr[loc]=arr[right];
            arr[right]=temp;
            loc=right;
        }
        if(flag!=1)
        {
            while((arr[loc]>=arr[left])&& (loc!=left))
            {
                left++;
            }
            if(loc==left)
            {
                flag=1;
            }
            else if(arr[loc]<arr[left])
            {
                temp=arr[loc];
                arr[loc]=arr[left];
                arr[left]=temp;
                loc=left;
            }
        }
    }
    return loc;
}
void quicksort(int arr[],int l,int r)
{
    int loc;
    if(l!=r)
    {
        loc=partition(arr,l,r);
        quicksort(arr,l,loc-1);
        quicksort(arr,loc+1,r);
    }
}

Answer 1

考虑这个函数:

void quicksort(int arr[], int l, int r)
{
    int loc;
    if(l!=r)
    {
        loc=partition(arr,l,r);
        quicksort(arr,l,loc-1);
        quicksort(arr,loc+1,r);
    }
}

在这里，我们的基本情况是 l==r .但是如果我们添加一个打印语句(和一些间距)

void quicksort(int arr[], int l, int r)
{
    if (l != r)
    {
        printf("left: %d, right: %d\n", l, r);
        fflush(stdout);
      //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

        int loc = partition(arr, l, r);
        quicksort(arr, l, loc - 1);
        quicksort(arr, loc + 1, r);
    }
}

并调用它

int arr[] = {4, 8, 1, 4, 5, 1, 8, 5, 7};
int arr_len = 9;
quicksort(arr, 0, arr_len - 1);

我们得到以下输出:

left: 0, right: 8
left: 0, right: 1
left: 0, right: -1
exited, segmentation fault

糟糕:left是 0 和 right是-1，我们调用了partition(arr, 0, -1);它立即使用语句 arr[right] 进行越界内存访问=> arr[-1] .

if (l < r)可能是这里的意图:

void quicksort(int arr[], int l, int r)
{
    if (l < r)
    {
        int loc = partition(arr, l, r);
        quicksort(arr, l, loc - 1);
        quicksort(arr, loc + 1, r);
    }
}

这使我们能够正确地建立递归的基本情况。

---

除此错误外，我建议在运算符之间使用空格，选择有意义的名称并避免不必要的变量。这方面的一个例子是 partition 的开头功能。如所写，它是:

int partition(int arr[],int l,int r)
{
    int left,right,temp,loc,flag;
    loc=left=l;
    right=r;
    flag=0;
// ...

但是l和 r刚刚被重新分配给 left和 right然后在函数的其余部分不用。像这样写:

int partition(int arr[], int left, int right)
{
    int temp;
    int loc = left;
    int flag = 0;
// ...

更清楚，但即使在这里，我们也应该移动 tmp (用于交换)到一个单独的函数或至少将其范围限定到用于避免陈旧值错误的 block 。我们应该#include <stdbool.h>因为这就是int flag实际上是(或使用早期返回来完全消除变量)并改进 loc变量名(它实际上是我们划分整数的基准):

int partition(int arr[], int left, int right)
{
    int pivot = left;
    bool flag = false; // or remove this completely in favor of `return`
// ...

这更干净。

此外，void main应该是 int main并使用明确的 return 0 .我建议使用现代编译器和开发环境并打开所有警告:

gcc quicksort.c -Wall -Wextra -Werror -O2 -std=c99 -pedantic

这揭示了 main 中未使用的变量，除其他外，通常可以减少痛点。

此外，我建议阅读 how to debug small programs它将为您提供必要的工具(包括概念和软件)来遍历和推理程序以定位错误。