0

マージソート用の MIPS アセンブリ言語コードを作成する必要があります。既にマージ関数を作成しましたが、再帰を使用する merge_sort 関数が非常に混乱しています。同じ参照Cコードを投稿しました。スタックを使用する必要があることは理解していますが、初心者で自分でそれを行うことができないため、何らかの助けをいただければ幸いです。

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
 }

 return 0;
}
4

1 に答える 1

0

ボトムアップで最初mergeのシングルトンのペア、次にソート済みの2つの長さのサブ配列のペア、次に4つの長さのサブ配列のペアなどをlog nループで同じ配列に渡してみませんか？

残っている問題は、を実装することmergeです。繰り返し呼び出されますが、再帰的には呼び出されません。もちろん、これmergeは入力領域を介してその出力を配列に書き戻す必要があり、おそらくその入力の一時的なコピーを作成して処理します。

void mrgsort( int a[], int n) // pseudo-code
{
    if( n < 1 ) return;
    int s1 = 1, s2 = 2;
    do
    {
        int i, k = n/s2, p1=0, p2=s1;
        for( i=0; i<k; ++i, p1+=s2, p2+=s2 )
        {
            merge(p1, p2); // merge chunks of size s1
        }
        //  deal with the edge ...
        if( i > 0 )
        {
            if( p2 < n ) merge_edge(p1,p2,n); // 2nd chunk shorter
        }
        s1 = s2;
        s2 = s2*2;
    } while( s2 <= n )
    if( s1 < n )
        merge_edge(0,s1,n);                   // 2nd chunk shorter
}

再帰はなく、ループは1つだけです。

于 2012-08-22T13:40:54.203 に答える