2

Cormen で提供されているヒープ ソート アルゴリズムを実装しようとしています。私のコードは次のとおりです。

    #include<stdio.h>
    #include<conio.h>
    void max_heapify(int *,int);
    void build_max_heap(int *,int);
    void heapsort(int *,int);
    void swap(int,int);
    int heapsize;
    int main()
    {
            int *arr,n,i;
            printf("Enter no. of elements = ");
            scanf("%d",&n);
            arr=(int *)malloc(sizeof(int)*n);
            for(i=0;i<n;i++)
            {
             printf("Enter array elements = ");
             scanf("%d",&arr[i]);
            }
            //heapsize = n;
            heapsort(arr,n);
            printf("\nAfter heapsort \n");
            for(i=0;i<n;i++)
            {
                printf("%d  ",arr[i]);
            }
        return 0;
    }
 void heapsort(int *arr,int len)
 {
   int i;
   build_max_heap(arr,len);
    for(i= len-1;i>=1;i--)
    {
        swap(&arr[0],&arr[i]);
        heapsize = heapsize -1;
        max_heapify(arr,0);
    }
 }
void max_heapify(int *arr,int i)
{
    int l=2*i,r=2*i+1,largest;
    if(l<heapsize && arr[l]>arr[i])
        largest = l;
    else
        largest = i;
    if(r<heapsize && arr[r]>arr[largest])
        largest = r;

    if(largest != i)
    {
        swap(&arr[i],&arr[largest]);
        max_heapify(arr,largest);
    }
     }
void build_max_heap(int *arr,int len)
{
    heapsize = len;
    int i;
    for(i =len/2;i>=0;i--)
    {
        max_heapify(arr,i);
    }
}
void swap(int *a ,int *b)
{
    int temp = *a;
    *a= *b;
    *b= temp;
}

私のコードで何が間違っているのか正確にわかりません。配列はソートされていません。実際、元の配列は印刷されています。どこが間違っていますか？

4

4 に答える 4

5

関数swapは引数を値で受け取ります。したがって、元の値がコピーされ、元の値ではなくコピーが交換されます。

swap( int *a, int *b)
于 2013-08-12T07:49:11.980 に答える
2

1）スワップを修正します。値渡しをしています。つまり、スワップが呼び出された後、何も変更されていません!

2) max_heapify 関数が間違っています。左右の子の計算が 1 ずれています。スワップすると、インデックスが配列値とスワップされます。

3) ヒープソート for ループが間違っています。最初の要素 (ヒープ内で最大のもの) を現在のヒープの最後のインデックスに配置し、ヒープのサイズを小さくして、最後の要素がヒープではなくソートされたリストの一部になるようにする必要があります。次に、最後の要素からではなく、ルートから下にパーキュレートします。次のようにする必要があります。

 for(i= len-1;i>=1;i--)
   {
    swap(arr[0],arr[i]);
    heapsize = heapsize -1;
    max_heapify(arr,0);
   }
于 2013-08-12T08:45:07.190 に答える
1

配列がまったくソートされていないことがわかります。段階的に完全なヒープ ソートを実行してみてください。したがって、デバッグ手法として、このコードのコピーを作成し、ヒープソートをバブル ソートに置き換えます。(バブルソートはコーディングがはるかに簡単です)。バブル ソートを機能させます。これには、パラメーターを渡し、ソートの前後に配列を出力することが含まれます。

次に、ヒープソートを行います。

于 2013-08-12T07:50:19.670 に答える