c - 11/12 测试用例，带辅助功能的快速排序

Question

这是没有通过的测试用例：

5 0 1 8 7

这是我的代码。

void swap(int* A, int* B)
{
  int t;
  t = *A;
 *A = *B;
 *B=t;
 }

void sorthelper(int * arr,int ind1, int ind2)
{
  int r = ind1+1;
  int w = ind1+1;
  // int i = 0;

  if (ind2 - ind1 <= 1)
    {
      return;
    }

  for(r=ind1+1; r<=ind2;r++)//For r starting at one bigger then pivot and less then the length(ind2), increment r by one each time
     {
       if(arr[r] < arr[ind1])// if read is bigger then pivot, increment w and swap w and r
         { 
           swap(&arr[w],&arr[r]);
           w++;            
         } 
     }
       swap(&arr[ind1], &arr[w-1]);//swap pivot with one less then write spot


       sorthelper(arr, ind1, w-1); 
       sorthelper(arr, w ,ind2); 

}      


void sort(int * arr, int length)
{
  int ind1 = 0;
  int ind2 = 0;
  ind2 = length-1;
  sorthelper(arr, ind1, ind2); 
  return;
}

我正在尝试编写一个快速排序算法（是的，这是硬件），除了这个测试用例之外，我所有的东西都在工作。我已经尝试了几个小时来解决这个错误，但我失败了。我曾尝试使用 GDB 来跟踪我的值，但无法确定此错误。任何人都可以提供任何意见吗？

排序函数首先运行，然后搜索助手是递归的并利用交换函数。

Answer 1

提示：当运行你的代码时，你会从第二行对 sorthelper 的递归调用中得到这样的调用。

sorthelper([0, 1, 5, 8, 7], 3, 4)

尽管它应该对 8 和 7 进行排序，但它什么也没做。想想为什么并修复它；）

Answer 2

在您的 sorthelper() 函数中，您将跳过数组只有两个元素的情况。请进行以下更改：

if (ind2 - ind1 <= 1) 

至

if (ind2 - ind1 < 1)

如果没有这个改变，一个包含两个元素数组的测试用例会给你一个错误：(8,7)！

Answer 3

两个问题。

1. 您假设如果 ind2 - ind1 == 1，则元素已经排序。这不是真的。这就是为什么 [8, 7] 分区最终没有排序的原因。
2. 分区时，您将下分区设置为从范围的开始到枢轴元素 (w-1)。它应该转到枢轴（w-2）之前的最后一个元素。