1

私は10個のintの配列を持っており、選択ソートを使用して計算すると、配列全体をソートするには約45回の比較が必要ですが、私の計算ではマージソートを使用してソートするのに何回かかるかわかりません.12回の比較が必要です... . ここで私は正しいですか、それとも間違っていますか?

前もって感謝します

これがマージ方法です

static void merge(int[] first, int[] second, int[] a)
    {
        int iFirst = 0;
        int iSecond = 0;
        int i = 0; 
        //moving the smaller element into a
        while(iFirst < first.length && iSecond < second.length)
        {
            if(first[iFirst] < second[iSecond])
            {
                a[i] = first[iFirst];
                iFirst++;
            }
            else
            {
                a[i] = second[iSecond];
                iSecond++;
            } 
            i++;             
        }
        counter += i;

        //copying the remaning of the first array
        while(iFirst < first.length)
        {
            a[i] = first[iFirst];
            iFirst++; i++;
        }
        //copying the remaining of second array
        while(iSecond < second.length)
        {
            a[i] = second[iSecond];
            iSecond++; i++;
        }        
    }
4

1 に答える 1

3

n-element 配列を -element 配列とマージするには、最悪の場合 (最良の場合) に比較mが必要です。n+m-1min{m,n}

したがって、10 要素の配列を半分に分割すると、最上位のマージで最大 9 回の比較が必要になります。2 つの 5 要素の半分は、それぞれ最大 4 回の比較が必要9 + 2*4 = 17です。5 要素の半分を 2 要素と 3 要素の部分に分割するには、最大 1 + 3 回の比較が必要なため、合計で最悪の場合は 25 回の比較 (9 + 2*4 + 2*3 + 2*1) になります。

                10(9)                             9
               /     \
              /       \
             /         \
            /           \
           /             \
          /               \
         /                 \
        5(4)               5(4)                   8
       /   \              /   \
      /     \            /     \
    3(2)     2(1)      3(2)     2(1)              6
   /   \    /   \     /   \    /   \
  2(1)  1  1     1   2(1)  1  1     1             2
 /   \              /   \
1     1            1     1
于 2012-05-26T21:10:29.323 に答える