2

マージソートとクイックソートの操作をカウントするプログラムを書いています。count++ をどこに置くべきかわかりません。（操作を数える）で。誰かがこれを手伝ってくれますか？

マージソートとクイックソートのコードは次のとおりです。

マージソート:

public void mergeSort(int [] data, int first, int n){

    int n1;
    int n2;

    if (n>1) {
        n1 = n/2;
        n2 = n-n1;           
        mergeSort(data,first,n1);
        mergeSort(data,first+n1,n2);
        merge(data,first,n1,n2);
    }

}//ends mergeSort method.

public void merge(int [] data, int first, int n1, int n2){
    int [] temp = new int[n1+n2];
    int copied = 0, copied1 = 0, copied2 = 0, i;

    while((copied1<n1) && (copied2<n2)){

        if(data[first+copied1] < data[first + n1 + copied2])
        temp[copied++] = data[first + (copied1++)];
        else
        temp[copied++] = data[first + n1 + (copied2++)];
    }

    while (copied1<n1)
        temp[copied++] = data[first + (copied1++)];
    while(copied2<n2)
        temp[copied++] = data[first + n1 + (copied2++)];

    for (i=0;i<n1+n2;i++)
        data[first+i] = temp[i];
}//ends merge method.

QUICK SORT のコードは次のとおりです。

public void quickSort(int data[], int left, int right){

    int index = partition(data, left, right);
    if (left < index - 1){              
        quickSort(data, left, index - 1);    
    }
    if (index < right){              
        quickSort(data, index, right);
    }
}//ends quickSort method.

int partition(int data[], int left, int right){

    int i = left, j = right;
    int tmp;
    int pivot = data[(left + right) / 2];

    while (i <= j)
    {
        while (data[i] < pivot)
        i++;
        while (data[j] > pivot)
        j--;
        if (i <= j)
        {

            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
            i++;
            j--;
        }
    }
    return i;
}//ends partition method.
4

3 に答える 3

4

あなたが++「操作」を持っているところならどこにでも置くべきです。あなたが操作と呼ぶものはあなた次第です。私は比較、スワップ、またはすべての行である可能性があります。あなたはあなたに何が適切かを決めることができます。

于 2012-10-01T18:47:57.080 に答える
1

マージソートでは、以下のメソッドがまさにそれを実行するメソッドです：-

merge(data,first,n1,n2);

だから、そこに1カウント++を入れてください。

そしてクイックソートで..それは：-

partition(data, left, right)

そこで、 count++を追加します。

他のメソッド呼び出し：-mergesort()そしてquicksort()単なる再帰呼び出しです..最終的には上記の2つmethodsだけになります。

しかし、最終的には、それはすべて、私の「操作を数える」という意味に依存しますoperation。

それはmethod execution、またはevery statement操作である可能性があります。またはループです。それは何を意味する可能性もあります。

于 2012-10-01T18:47:56.917 に答える
1

「big O」分析を行っていると仮定すると、「操作数」は最も内側のループの反復回数です。

  • あなたの QuickSort の例では、それは簡単です: 後にカウンターを置きますwhile (i <= j)
  • MergeSort の例では、各whileループにカウンターを配置する必要があります (これらのループを詳しく見ていませんが、必要以上のことをしているようです)。

このカウントは、実行している操作の実際の数を示すものではなく、操作の「大きな」数です。MergeSort と QuickSort は同じ "big O" 特性を持っている可能性がありますが (したがって、同様の数になるはずです)、最も内側のループ内で実行される作業の量は異なります。

于 2012-10-01T19:57:25.623 に答える