无法在快速排序中正确传递数组

Here is my program it is compiling and running without syntax errors.How ever it does not sort the array.The problem lies in where I am passing the array in function

这是我的程序,它正在编译和运行没有语法错误。如何它不排序数组。问题在于我在函数中传递数组的位置

#include<stdio.h>
#include<string.h>
int partition (int *,int,int);
void quicksort (int *,int,int);
static int call=0;
int main()
{
int i,j,choice;
int length;
int a[]={81, 12, 90, 3, 49, 108, 47};
i=0;

length=sizeof(a)/sizeof(a[0]);
quicksort(a,0,length-1);
printf("the sorted array is\n");
for(i=0;i<length;i++)
 printf (" %d ",a[i]);
}
int partition(int *num,int p,int r)
{
 int x,j,i,temp,bak;
  x=num[r];
  i=p-1;
       for(j=0;j<=r-1;j++)
  { 
         if(num[j]<=x)
     {
      i=i+1;
       temp=num[i];
       num[i]=num[j];
       num[j]=temp;


      {
       printf(" %d",num[bak]);
        }

     }  
  }
  num[i+1]=num[r];

 return i+1;
}

void quicksort (int *num,int p,int r)
{ 
 int q;
 if (p<r)
  {
    call++;

    q=partition(num,p,r);
        quicksort(num,p,q-1);
        quicksort(num,q+1,r);
  }
}    

The above way of passing array in functions is that right that is what I want to know because that is giving problem in function partition.

在函数中传递数组的上述方法是正确的,这是我想知道的,因为这在函数分区中给出了问题。

Inside the function partition when swapping happens then I tried printing the array there itself (it is not sorted array but just to see upto what point things reached) then I saw that only 2 or 3 elements of array which I had passed are being printed and rest of the array is lost some where.So my doubt is array is not being passed properly.

当交换发生时在函数分区内部,然后我尝试在那里打印数组(它不是排序数组,只是为了看到事情达到了什么点)然后我看到只有2或3个数组的元素被打印出来并且数组的其余部分丢失了一些where.So我怀疑数组是不是正确传递。

To be able to see as what is the problem with array passing in a function I wrote a smaller program ka1.c

为了能够看到函数中传递数组的问题,我编写了一个较小的程序ka1.c

#include<stdio.h>
void pass(int *);
int main ()
{
int a[]={3,5,61,32,12};
pass(a);
}
void pass (int *num)
{
int i,j;
 j=sizeof(num)/sizeof(num[0]);
 for (i=0;i<j;i++)
 printf(" %d",num[i]);
}

Now when I run the above code I get output just

现在,当我运行上面的代码时,我得到输出

 3 5

I was expecting the complete array to be printed in output of ka1.c. Where as if you notice rest of the array is not getting printed.Where did that go? I have used the same logic in quicksort also hence I feel the error is same in both cases.

我期待在ka1.c的输出中打印完整的数组。好像你注意到阵列的其余部分没有被打印出来。那去哪儿了?我在quicksort中也使用了相同的逻辑,因此我觉得两种情况下的错误都是一样的。

UPDATE1
After the comment below I checked the length of array recieved in quicsort.c paritition function via

UPDATE1在下面的评论之后,我检查了quicsort.c paritition函数中收到的数组的长度

sizeof(num)/sizeof(num[0]);

and found of original array

并找到原始数组

int a[]={81, 12, 90, 3, 49, 108, 47};

which is having length 7 here when I passed it in the function partition the length is only 2. The same is case with program ka1.c So why only length is 2 in both cases?

当我在函数分区中传递长度为2时,长度为7的长度仅为2.程序ka1.c也是如此。那么为什么在两种情况下只有长度为2?

UPDATE2
As the suggestions given below now I have passed on the length also

更新2正如下面给出的建议,我也传递了长度

#include<stdio.h>
#include<string.h>
int partition (int *,int,int,int);
void quicksort (int *,int,int,int);
static int call=0;
int main()
{
int i,j,choice;
int length;
int a[]={81, 12, 90, 3, 49, 108, 47};
i=0;
printf("the sorted array is\n");
length=sizeof(a)/sizeof(a[0]);
printf("length of array %d\n",length);
printf("quick sort called in main\n");
quicksort(a,0,length-1,length);
for(i=0;i<length;i++)
 printf (" %d ",a[i]);
}
int partition(int *num,int p,int r,int june)
{
 int x,j,i,temp,bak,length;
  x=num[r];
  i=p-1;
  bak=0;
  printf("inside the partition\n");
 printf("length of june recieved =%d \n",june);
  for(j=0;j<=r-1;j++)
  { 
    if(num[j]<=x)
     {
      i=i+1;
       temp=num[i];
       num[i]=num[j];
       num[j]=temp;
    printf("printing array after swap\n");
      for(;bak<7;bak++)
      {
           printf(" %d ",num[bak]);
          }
     }  
  }
  num[i+1]=num[r];

 return i+1;
}

void quicksort (int *num,int p,int r,int june)
{ 
 int q,bbc,ccd;
 if (p<r)
  {
    call++;
         printf("partition called  %d times p=%d r=%d\n",call,p,r);
    printf("before sending to function length of june=%d \n",june);
    q=partition(num,p,r,june);
    bbc=q-1-p+1;
        quicksort(num,p,q-1,bbc);
        ccd=r-q-1+1;
        quicksort(num,q+1,r,ccd);
  }
}

But the program is still failing to print the sorted array. You can compile and run the above code.

但该程序仍然无法打印排序的数组。您可以编译并运行上面的代码。

SOLVED
Finally with help of replies below I have been able to solve the above problem. The mistake lied in function partition in statement

解决了最后在下面的回复帮助下,我已经能够解决上述问题。错误在语句中的函数分区中撒谎

  for (j = 0; j <= r - 1; j++)

instead it should have been

相反应该是

  for (j = p; j <= r - 1; j++)

note j=p and j=0 here

注意这里j = p和j = 0

j=0

is wrong since when recursively second partition is tried to be sorted it started disturbing the first partition and hence the result was also wrong.

是错误的,因为当递归第二个分区被尝试排序时,它开始扰乱第一个分区,因此结果也是错误的。

In this program I faced a problem in using gdb to debug a recursive function. Please check this thread also Debugging recurssion was quite tricky.

在这个程序中,我遇到了使用gdb调试递归函数的问题。请检查此线程还调试recurssion非常棘手。

SO the correct code is

所以正确的代码是

#include<stdio.h>
#include<string.h>
int partition (int *, int, int, int);
void quicksort (int *, int, int, int);
static int call = 0;
int
main ()
{
  int i, j, choice;
  int length;
  int a[] = { 81, 12, 90, 3, 49, 108, 47 };
  i = 0;
  printf ("the sorted array is\n");
  length = sizeof (a) / sizeof (a[0]);
  printf ("length of array %d\n", length);
  printf ("quick sort called in main\n");
  quicksort (a, 0, length - 1, length);
  for (i = 0; i < length; i++)
    printf (" %d ", a[i]);
}

int
partition (int *num, int p, int r, int june)
{
  int x, j, i, temp, bak, length;
  x = num[r];
  i = p - 1;
  bak = 0;
  for (j = p; j <= r - 1; j++)
    {
      if (num[j] <= x)
    {
      i = i + 1;
      temp = num[i];
      num[i] = num[j];
      num[j] = temp;
    }
    }
  temp=num[i+1];
  num[i + 1] = num[r];
  num[r]=temp;
  return i + 1;
}

void
quicksort (int *num, int p, int r, int june)
{
  int q, bbc, ccd;
  if (p < r)
    {
      call++;
      q = partition (num, p, r, june);
      bbc = q - 1 - p + 1;
      quicksort (num, p, q - 1, bbc);
     ccd=r-q+1;
      quicksort (num, q + 1, r, ccd);
    }
}

3 个解决方案

#1

The problem is in the way you are calculating the length of teh array.......try simply giving the number of elements in the array as the parameter for the quicksort method....i guess u will have the right answer... and also i agree to the point made....try and passing the length of the array with the array.....try both and tell me which works...:) NEW CODE:

问题在于你计算数组的长度.......尝试简单地给出数组中元素的数量作为quicksort方法的参数....我猜你会得到正确的答案...而且我同意所提出的观点....尝试并使用数组传递数组的长度.....尝试两个并告诉我哪些工作... :)新代码:

#include<stdio.h>
#include<string.h>
//int partition (int *,int,int);
void q_sort(int*,int,int);
void quicksort (int *,int);
static int call=0;
int main()
{
int i,j,choice;
int length;
int a[]={81, 12, 90, 3, 49, 108, 47};
i=0;
printf("the sorted array is\n");
length=sizeof(a)/sizeof(a[0]);
printf("length of array %d\n",length);
printf("quick sort called in main\n");
quicksort(a,length);
for(i=0;i<length;i++)
 printf (" %d ",a[i]);
}
/*int partition(int *num,int p,int r)
{
 int x,j,i,temp,bak,length;
  x=num[r];
  i=-1;
  bak=0;
  printf("inside the partition\n");
  for(j=0;j<=r-1;j++)
  {
    if(num[j]<=x)
     {
      i=i+1;
       temp=num[i];
       num[i]=num[j];
       num[j]=temp;
    printf("printing array after swap\n");
      for(;bak<7;bak++)
      {
           printf(" %d ",num[bak]);
          }
     }
  }
  num[i+1]=num[r];

 return i+1;
}
*/
/*void quicksort (int *num,int p,int r)
{
 int q,bbc,ccd;
 if (p<r)
  {
    call++;
         printf("partition called  %d times p=%d r=%d\n",call,p,r);
    q=partition(num,p,r);
    bbc=q-1-p+1;
        quicksort(num,p,q-1);
        ccd=r-q-1+1;
        quicksort(num,q+1,r);
  }
}*/
void quicksort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

#2

You need to put a ; at the end of the function declaration before main:

你需要放一个;在main之前的函数声明结束时:

void pass(int *) ;
                 ^

#3

You have to pass the size of the array along with the array itself. The function receiving the array cannot determine its size. The receiving function only sees num as a pointer, so when you use sizeof(num) it returns the size of the pointer num, not the size of the memory allocated for the array in the main function. So, you have to do something like this:

您必须将数组的大小与数组本身一起传递。接收阵列的函数无法确定其大小。接收函数只将num视为指针,因此当使用sizeof(num)时,它返回指针num的大小,而不是main函数中为该数组分配的内存大小。所以,你必须做这样的事情:

#include<stdio.h>

void pass(int *, int);
int main ()
{
    int a[]={3,5,61,32,12};
    int length;
    length = sizeof(a)/sizeof(a[0]);
    pass(a, length);
}
void pass (int *num, int size)
{
    int i;  
    for (i=0;i<size;i++)
        printf(" %d",num[i]);
}

This post explains a similar issue in more detail: Passing an array as an argument in C++

这篇文章更详细地解释了一个类似的问题:在C ++中将数组作为参数传递