2

私は現在、Java で実装されたときにさまざまなアルゴリズムがどのように動作するかを観察する分析プロジェクトに取り組んでいます。Mergesort アルゴリズムを実装するコードをオンラインから入手したので、このコードをランダムに生成された 10,000 個の整数 (1 から 100,000 の間) の配列に対して実行し、スワップと比較が行われた回数を記録する必要があります。

コードのどの時点で、スワップと比較をカウントする変数をインクリメントするか正確にはわかりません。期待値はどうなりますか？Mergesort の最良、最悪、平均のケースはすべて nlog(n) であるため、スワップと比較の合計は 10,000*(log base 2 of 10,000) approx = 138,000 を期待する必要がありますか?

コードは次のとおりです。元の配列が変更された場合にのみスワップが発生すると推測していますが、比較についてはよくわかりません。

void MergeSort(int low, int high)
   // a[low : high] is a global array to be sorted.
// Small(P) is true if there is only one element to
// sort. In this case the list is already sorted.
{
   if (low < high) { // If there are more than one element
          // Divide P into subproblems.
          // Find where to split the set.
          int mid = (low + high)/2;
          // Solve the subproblems.
          MergeSort(low, mid);
          MergeSort(mid + 1, high);
          // Combine the solutions.
          Merge(low, mid, high);
   }
}

   void Merge(int low, int mid, int high)
 // a[low:high] is a global array containing two sorted
 // subsets in a[low:mid] and in a[mid+1:high]. The goal
 // is to merge these two sets into a single set residing
 // in a[low:high]. b[] is an auxiliary global array.
 {
     int h = low, i = low, j = mid+1, k;
   while ((h <= mid) && (j <= high)) {
      if (a[h] <= a[j]) { b[i] = a[h]; h++; }
      else { b[i] = a[j]; j++; } i++;
   }
   if (h > mid) for (k=j; k<=high; k++) {
                   b[i] = a[k]; i++;
                }
   else for (k=h; k<=mid; k++) {
           b[i] = a[k]; i++;
        }
   for (k=low; k<=high; k++) a[k] = b[k];

}

4

3 に答える 3

6

コードのどの時点で、スワップと比較をカウントする変数をインクリメントするか正確にはわかりません。

スワップ操作と比較操作用のヘルパー メソッドを作成することをお勧めします。これにより、インクリメント カウンター コードの適切な場所が得られます。

Mergesort の最良、最悪、および平均のケースはすべて nlog(n)であるため、これは、スワップと比較の合計が 10,000 (10,000 の対数底 2) 約 = 138,000 になると予想する必要があることを意味しますか?*

期待できることは、入力のサイズがnである場合、比較の数がn log(n)に比例することです。

于 2012-07-29T21:08:52.547 に答える
1

あなたのマージ関数で、スワップの合計数を持つ変数 count を追加しました

  while ((h <= mid) && (j <= high)) {
      if (a[h] <= a[j]) { b[i] = a[h]; h++; }
      else { b[i] = a[j]; j++; count+=mid-h+1; } i++;
  }
于 2013-08-02T23:03:37.077 に答える
0

私は実際にアルゴリズムとデータ構造の宿題のためにこれをやっています。スレッドは少しほこりっぽいですが、それを使用できる人のために、これは私が得たものです:

Merge メソッドで

while ((h <= mid) && (j <= high)) {
  if (a[h] <= a[j]) { b[i] = a[h]; h++; }
  else { b[i] = a[j]; j++; } i++;
}

if ステートメントは比較が行われている場所です。else ステートメントに行っても、if ステートメントが失敗したために比較も行われると言いたいところです。

else ステートメントは、スワップが開始される場所です。else ステートメントにカウンターを配置すると、すべてのスワップがカウントアップされます。配列を 2 回チェックして、これを確認しました。1 回はソートされていないとき、もう 1 回はソートされたときです。私はこれについて 100% ではありませんので、フィードバックをいただければ幸いです。文字列を並べ替えているため、私の割り当てで見るのが少し簡単です。これらは、私の割り当てから、上記に投稿された Merge 関数の同じ行です。

while(leftPos<=leftEnd && rightPos<=rightEnd)
{
    mergeSortComparisons++;

    if (a[leftPos].compareTo(a[rightPos]) <= 0)     
        tmpArray[tmpPos++]=a[leftPos++];

    else 
    {
        tmpArray[tmpPos++]=a[rightPos++];
        mergeSortSwaps++;
    }
}

mergeSortSwaps と mergeSortComparisons は、コンストラクターで設定されるクラス変数です。メソッドを思い出せばリセットできます。

于 2012-11-07T02:32:09.987 に答える