无法调试我的快速排序程序

#include <stdio.h> 


int Partition (int * A, int p, int r) 
{ 
    printf("PARTITION\n"); 
    int x=0; 
    x=A[r]; 
    int i=p-1, j=r+1; 
    int temp; 
    int k=0; 
    while(1) 
    { 
     printf("\tLOOP\n"); 
     do 
     { 
      j=j-1; 
     } while(A[j]>x) ; 

     do 
     { 
      i=i+1; 
     } while(A[i]<x); 

     if (i<j) 
     { 
      temp=A[i]; 
      A[i]=A[j]; 
      A[j]=temp; 
     } 
     else 
     { 
      printf ("ARRAY: "); 
      for (k=p; k<=r; k++) 
       printf ("%d,",A[k]); 
      printf ("\nRETURNING : %d \n", j); 

      return j; 
     } 

    } 
} 
void QuickSort(int * A, int p, int r) 
{ 
    int q; 
    if (p<r) 
    { 
     q = Partition (A,p,r); 
     QuickSort(A,p,q); 
     QuickSort(A,q+1,r); 
    } 

} 



int main() 
{ 
    int A[9] = {9,2,4,1,7,8,3,5,6}; 
    int i; 
    QuickSort(A,0,8); 
    for (i=0;i<=8;i++) 
    { 
     printf("%d ", A[i]); 
    } 
    return 0; 
}

上GDB一小时后，我已经缩小这一计划的问题到这一点：无法调试我的快速排序程序

我的阵列从0-9有索引。它首先被分区为0-5和6-9。然后0-5部分被分区为0-2和3-5 然后0-2部分被分区为0-0和1-2 现在由于if (p<r)条件，0-0部分被跳过，但是程序会为另一部分调用分区（A，1,2）。现在这里是程序卡住的地方，它一直不断地调用Partition（A，1,2），因为它一直返回'2'作为枢轴索引。

这是怎么发生的？我无法理解程序在逻辑上哪里出了问题，我遵循了互联网上各个地方给出的确切的伪代码。

编辑：我能够通过使用if (i<=j)而不是if (i<j)在Partition解决问题。它迫使j将递减一次，但那只是因为我很幸运地选择了do while而不是while。我仍然困惑为什么直接执行Quicksort伪代码不起作用。

来源

2013-03-15 user1265125

你可以比较的基准C语言实现[通过Rosetta代码]（http://rosettacode.org/wiki/Sorting_algorithms/Quicksort您的实现#C） – Michael 2013-03-15 10:47:46

确切的伪代码？ QuickSort上有许多不同的伪代码，将链接指向您使用的伪代码将是明智的。此外，如果您完全按照准确的伪代码执行，则您的QuickSort将会正常工作（除非您设法为QuickSort找到破损的伪代码）。由于它不起作用，我们必须推断你是一个人，而不是一台机器，并且你在将伪代码翻译成C代码时犯了一个错误。 – 2013-03-15 13:13:21

你已经在你的代码所做的很多错误。

QuickSort(A,p,q);是QuickSort(A,p,q-1);
int i=p-1, j=r+1;没有必要。
您的partition()，将需要一个额外的变量来保持枢纽。
while(A[i]<x) ;应该是while(A[i] <= x[piv] && i<r);
在你的程序中，你已经错过了一个算法步骤，其中数据库变量在数据透视表中与最后一个数组变量交换，没有这个关键步骤，就没有进行排序。

这里是你的节目，与校正时进行

#include <stdio.h> 


int Partition (int *A, int p, int r) 
{ 
    printf("PARTITION\n"); 
    int i=p, j=r ,piv=p ; 
    int temp; 

    while(i<j) 
    { 
     printf("\tLOOP\n"); 

     while(A[i] <= A[piv] && i<r) 
      i++; 

     while(A[j]>A[piv]) 
      j--; 


      if (i<j) 
      { 
       temp=A[i]; 
       A[i]=A[j]; 
       A[j]=temp; 
      } 
    } 

/*Crucial step that you happen to miss*/ 
     temp=A[piv]; 
     A[piv]=A[j]; 
     A[j]=temp; 

return j; 
} 


void QuickSort(int *A, int p, int r) 
{ 
    int q; 
    if (p<r) 
    { 
     q = Partition (A,p,r); 
     QuickSort(A,p,q-1); 
     QuickSort(A,q+1,r); 
    } 
} 



int main() 
{ 
    int A[9] = {9,2,4,1,7,8,3,5,6}; 
    int i; 
    QuickSort(A,0,8); 
    for (i=0;i<=8;i++) 
    { 
     printf("%d ", A[i]); 
    } 
    return 0; 
}

来源

2013-03-15 12:15:13

无法调试我的快速排序程序

回答

相关问题