0

バブル、挿入、マージの 3 つの並べ替え方法の jsperf.com テストを作成しました。リンク

テストの前に、0 から 1Mln までの乱数でソートされていない配列を作成します。テストのたびに、挿入ソートはマージ ソートよりも高速であることが示されます。マージソート時間 O(n log(n)) で、挿入およびバブルソートのテスト結果が O(n^2) である場合、そのような結果の理由は何ですか?

4

2 に答える 2

0

Amadan がコメントしたように、マージ ソートでは、ソートされる配列と同じサイズの割り当てを 1 回だけ行うのが最善です。トップダウン マージ ソートは再帰を使用してマージで使用されるインデックスを生成しますが、ボトムアップは再帰をスキップし、反復を使用してインデックスを生成します。ほとんどの時間はサブ配列の実際のマージに費やされるため、より大きな配列 (100 万要素以上) でのトップダウンの余分なオーバーヘッドは約 5% にすぎません。

多少最適化されたボトムアップ マージ ソートの C++ コードの例。

void MergeSort(int a[], size_t n)           // entry function
{
    if(n < 2)                               // if size < 2 return
        return;
    int *b = new int[n];
    BottomUpMergeSort(a, b, n);
    delete[] b;
}

size_t GetPassCount(size_t n)               // return # passes
{
    size_t i = 0;
    for(size_t s = 1; s < n; s <<= 1)
        i += 1;
    return(i);
}

void BottomUpMergeSort(int a[], int b[], size_t n)
{
size_t s = 1;                               // run size 
    if(GetPassCount(n) & 1){                // if odd number of passes
        for(s = 1; s < n; s += 2)           // swap in place for 1st pass
            if(a[s] < a[s-1])
                std::swap(a[s], a[s-1]);
        s = 2;
    }
    while(s < n){                           // while not done
        size_t ee = 0;                      // reset end index
        while(ee < n){                      // merge pairs of runs
            size_t ll = ee;                 // ll = start of left  run
            size_t rr = ll+s;               // rr = start of right run
            if(rr >= n){                    // if only left run
                rr = n;
                BottomUpCopy(a, b, ll, rr); //   copy left run
                break;                      //   end of pass
            }
            ee = rr+s;                      // ee = end of right run
            if(ee > n)
                ee = n;
            // merge a pair of runs
            BottomUpMerge(a, b, ll, rr, ee);
        }
        std::swap(a, b);                    // swap a and b
        s <<= 1;                            // double the run size
    }
}

void BottomUpCopy(int a[], int b[], size_t ll, size_t rr)
{
    while(ll < rr){                         // copy left run
        b[ll] = a[ll];
        ll++;
    }
}

void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
    size_t o = ll;                          // b[]       index
    size_t l = ll;                          // a[] left  index
    size_t r = rr;                          // a[] right index
    while(1){                               // merge data
        if(a[l] <= a[r]){                   // if a[l] <= a[r]
            b[o++] = a[l++];                //   copy a[l]
            if(l < rr)                      //   if not end of left run
                continue;                   //     continue (back to while)
            while(r < ee)                   //   else copy rest of right run
                b[o++] = a[r++];
            break;                          //     and return
        } else {                            // else a[l] > a[r]
            b[o++] = a[r++];                //   copy a[r]
            if(r < ee)                      //   if not end of right run
                continue;                   //     continue (back to while)
            while(l < rr)                   //   else copy rest of left run
                b[o++] = a[l++];
            break;                          //     and return
        }
    }
}
于 2015-11-02T09:20:31.597 に答える
0

これ以上テストせずに、暫定的な回答:

挿入ソートはかなり最適化されています。要素を切り替えるだけです。マージソートは、 を使用して新しい配列をインスタンス化し、 and を使用して新しい[]配列を作成します。これは、言うまでもなく、メモリ管理のオーバーヘッドが大きく、それらの内部に暗黙的なループがあります (ネイティブコードではありますが)。マージソートは、インプレースで実行すると効率的です。すべてのコピーが進行しているため、速度が大幅に低下するはずです。sliceconcatconcatslice

于 2015-11-02T05:39:26.327 に答える