计算快速排序中的比较：错误答案

Question

我已经编写了代码来计算在 QuickSort 中完成的比较次数。

每当对长度为 m 的数组执行快速排序时，算法会将比较次数增加 m-1（因为 pivot 将与除自身以外的所有内容进行比较）。

枢轴的选择始终是数组的第一个元素。

当我尝试在包含 10000 个条目的数组上使用它时，它给出了错误的答案。

正确答案应该是 162085.

数据集的link如下： https://drive.google.com/file/d/0B0D_kFnzj_RrYm9NT0lrM3JfN2c/view?usp=sharing

总比较存储在 x 中。

 #include<stdio.h>
  long long x=0;
  int size=10000;
  int A[10000];
  int B[10000];

  void quicksort(int A[],int begin,int end)
  {
  if(begin<end){
  int i=begin;
  int j=end;
  int k;
  int pivot=begin;

  for(k=begin+1;k<=end;k++)
  {
  if(A[k]>A[pivot])
  {
  x++;
  B[j]=A[k];
  j--;
  }
  else
  {
  x++;
  B[i]=A[k];
  i++;
  }
  }

  B[i]=A[pivot];

  for(k=begin;k<=end;k++)
  {
  A[k]=B[k];
  }

  quicksort(A,begin,i-1);
  quicksort(A,i+1,end);
  }
  else
  {
  if((end-begin)==1) x++;
  }
  }

  int main()
  {

  FILE *myFile;
  myFile = fopen("QuickSort.txt", "r");


  int i;
  for (i = 0; i < 10000; i++)
  {
  fscanf(myFile, "%d", &A[i]);
  }

  quicksort(A,0,size-1);

  for(i=0;i<size;i++)
  {
  printf("%d\n",A[i]);
  }

  printf("%lld",x);
  }

Answer 1

这部分是错误的：

for(k=begin+1;k<=end;k++)
{
    if(A[k]>A[pivot])
    {
        x++;
        B[j]=A[k];
        j--;
    }
    else
    {
        x++;
        B[i]=A[k];
        i++;
    }
}

您不必从头到尾。你只应该从 begin 到 i>j.

参见 link：https://en.wikipedia.org/wiki/Quicksort

有趣的台词是：

do
    i := i + 1
while A[i] < pivot
do
    j := j – 1
while A[j] > pivot
if i >= j then
    return j
swap A[i] with A[j]

c/c++

i = begin;
j = end;
while(true)
{
    while(i< end && A[i] < A[pivot])
    {
        i++;
    }
    while(j> begin && A[j] >= A[pivot])
    {
        j--;
    }
    if(i<j)
    {
        int temp = A[i]; //std::swap(A[i],A[j]);
        A[i] = A[j];
        A[j] = temp;
    else
    {
       break;
    }
}

在这段代码中，我不使用 B，因为快速排序是一种 "inplace" 算法，因此我们不需要将结果保存到不同的数组中

计算快速排序中的比较：错误答案

Counting Comparisions in Quicksort: Wrong answer

c

sorting

quicksort