0

マージソートを実装する小さなプロジェクトを書きます。これは私のコードです：

template <typename T>
void merge(T arr[], int begin, int mid, int end)
{
    int len = end - begin + 1;
    T *temp = new T[len];
    int i = begin;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= end)
    {
        if(arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid)
        temp[k++] = arr[i++];
    while(j <= end)
        temp[k++] = arr[j++];

    memcpy(arr + begin, temp, len*sizeof(T));
}


//merge sort
template <typename T>
void mergeSort(T arr[], int begin, int end)
{
    if (begin >= end)
        return;

    int mid = (end + begin) / 2;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, begin, mid, end);
}

int main()
{
    const int N = 10;
    int arr[N];
    for_each(arr, arr + N, [](int &val){ val = rand() % 100; });

    copy(arr, arr+N, ostream_iterator<int>(cout, " "));
    cout<<endl;

    mergeSort(arr, 0, N - 1);

    copy(arr, arr+N, ostream_iterator<int>(cout, " "));
    cout<<endl;
}

正しい答えが返ってきた時もあれば、間違った答えを返した時もあった。この問題は私を何度も混乱させます。いつバグを見つけるのに役立ちますか?

4

2 に答える 2

0

コードで犯した間違いは、ソートする配列の長さを計算するときです。確かint len = end - begin;に長さは9ですが、配列には10個の要素が含まれています。

関数にインデックスを送信するときは注意が必要です。すべてのstd::関数は反復子で機能し、end反復子は常に最後の要素の 1 つ後ろを示します。

これを念頭に置いてコードを変更mergeSort(arr, 0, N);し、メインを呼び出して、他の関数が正しく動作するようにすることをお勧めします。

于 2013-08-08T12:25:03.343 に答える