2 
#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 で 1 時間使用した後、このプログラムの問題を次のように絞り込みました。

私の配列には 0 ～ 9 のインデックスがあります。最初に 0 ～ 5 と 6 ～ 9 に分割されます。次に、0 ～ 5 の部分が 0 ～ 2 および 3 ～ 5 として分割されます 次に、0 ～ 2 の部分が 0 ～ 0 および 1 ～ 2 として分割されます 0 ～ 0 の部分はif (p<r)条件のためにスキップされますが、プログラムは Partition を呼び出します(A,1,2) 他の部分。ここでプログラムがスタックします。ピボット インデックスとして '2' を返し続けるため、Partition (A,1,2) を何度も呼び出し続けます。

なぜこうなった？プログラムのどこが間違っているのか論理的に理解できません。インターネット上のさまざまな場所で提供されている正確な疑似コードに従いました。

編集: inif (i<=j)の代わりに使用して問題を解決できました。もう一度デクリメントする必要がありますが、それは私が幸運にもの代わりにを選択したからです。Quicksort 疑似コードの直接実装がなぜ機能しなかったのか、いまだに困惑しています。if (i<j)Partitionjdo whilewhile

4

1 に答える 1

1

コードで多くの間違いを犯しました。

  • 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-15T12:15:13.027 に答える