2

stlライブラリを使用してマージソートアルゴリズムを作成しようとしていますが、いくつか問題があります。以下は私が使用しているコードです

template <typename Item, typename SizeType>
void merge_sort(Item array[], SizeType size){
    size_t n1; //Size of the first subarray
    size_t n2; //Size of the second subarray

    if(size > 1){
        //Compute the size of the subarrays
        n1 = size/2;
        n2 = size - n1;

        //create the temp array.
        int* n1Temp = new int[n1];
        int* n2Temp = new int[n2];
        int i;
        for(i = 0; i < n1; i++)
            n1Temp[i] = array[i];
        for(i = 0; i < n2; i++)
            n2Temp[i] = array[i + n1];

        //recursive calls
        merge_sort(n1Temp, n1);//sort from array[0] through array[n1 - 1] 
        merge_sort(n2Temp, n2);//sort from array[n1] to the end

        //Merge the two sorted halves.
        vector<int> v(array, array + size);
        merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, v.begin());     
        copy(v.begin(), v.end(), array);//copy the vector back to the array

        delete[] n1Temp;
        delete[] n2Temp;
    }
}

コードは正常にソートされますが、問題は、マージソート呼び出しごとにベクトルが作成されるため、O（n \ log n）ではなくO（n ^ 2）アルゴリズムのように動作することです（私は思います）。ベクトルを削除して、以下に示すマージ関数で配列を使用してみました

    //Merge the two sorted halves.
    int* finalArray = new int[n1 + n2];
    merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, begin(finalArray)); 
    array = finalArray;

しかし、これは私にエラー以外の何物も与えません。マージソートアルゴリズムを救済するためにできることはありますか？

4

1 に答える 1

4

Vaughn と user93353 の両方が指摘したように、各マージ ポイントでターゲット アレイに直接マージできるはずです。ただし、 std::vector<> を使用して、これを自分で大幅に簡単にすることができます。

また、一時配列は直接型「int」であり、それがテンプレートパラメーターの型になることを意図していたと確信していますItem。このパラメーターが何のためのものかはわかりませんSizeTypeが、特別なアイデアがある場合に備えて残しました。それが何であれ、それは以下と互換性がある方が良いですsize_t:

template <typename Item, typename SizeType>
void merge_sort(Item array[], SizeType size)
{
    if(size > 1)
    {
        //Compute the size of the subarrays
        size_t n1 = size/2;

        //create the temp array
        std::vector<Item> n1Temp(array, array+n1);
        std::vector<Item> n2Temp(array+n1, array+size);

        //recursive calls
        merge_sort(&n1Temp[0], n1);       //sort array[0] through array[n1-1]
        merge_sort(&n2Temp[0], size-n1);  //sort array[n1] through array[size-1]

        // merge the sorted halves
        std::merge(n1Temp.begin(), n1Temp.end(),
                   n2Temp.begin(), n2Temp.end(), array);
    }
}

上記の手法は、コピーによってサブシーケンスをトップダウンで分割し、分割コピーを元の配列にインプレースでマージします。元の配列で分割を行い、一時空間にマージしてからコピーすることにより、このアルゴリズムを1つのサブリスト割り当て時間(ただし、スペースは少なくなりません)で減らすことができます。これは、最初にやろうとしていたと思います:

template <typename Item>
void merge_sort(Item ar[], size_t n)
{
    if (n > 1)
    {
        // Compute the size of the subarrays
        size_t n1 = n/2;

        // invoke recursion on the submerges
        merge_sort(ar, n1);      //sort array[0] through array[n1-1]
        merge_sort(ar+n1, n-n1); //sort array[n1] through array[size-1]

        // create merge-buffer
        std::vector<Item> mrg;
        std::merge(ar, ar+n1, ar+n1, ar+n, back_inserter(mrg));
        std::copy(mrg.begin(), mrg.end(), ar);
    }
}

一般的な反復子ベースのソリューション

より柔軟な一般的なソリューションとして、Item ポインタではなくイテレータに基づいてマージソートを定義できます。少し複雑になりますが、利点は非常に std-lib っぽいです。

template <typename Iterator>
void merge_sort(Iterator first, Iterator last)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    typedef typename std::iterator_traits<Iterator>::difference_type difference_type;

    difference_type n = std::distance(first, last)/2;
    if (n == 0)
        return;

    // invoke recursion on the submerges
    merge_sort(first, first + n);
    merge_sort(first + n, last);

    // create merge-buffer
    std::vector<value_type> mrg(std::distance(first, last));
    std::merge(first, first+n, first+n, last, mrg.begin());
    std::copy(mrg.begin(), mrg.end(), first);
}

最後に、大量の固定長の C 配列を並べ替えていることに気付いた場合は、次の情報が役立つことがあります (上記の一般イテレータ ソリューションを使用します)。

// front-loader for C arrays
template<typename Item, size_t N>
void merge_sort(Item (&ar)[N])
{
    merge_sort(std::begin(ar), std::end(ar));
}

これにより、次のコードがかなり便利になります。

int arr[1024];
... fill arr ...
merge_sort(arr);
于 2012-12-01T18:49:42.537 に答える