1

コードを実行すると、配列に何かを追加するのを間違えたときに通常そこにある、多くの繰り返しの数字や大きな負の値が得られます。問題は、マージ自体を行っているときだと思います。

void mergeSort( int list[], int lb, int ub )
{
    int mid;
    if ( lb < ub )
    {
        mid = (lb + ub) /  2;
        mergeSort(list, lb, mid);
        mergeSort(list, mid + 1, ub);
        myMerge(list, lb, mid , ub);
    }
}

template <class M>
void myMerge( M list[], int lb, int mid, int ub )
{
   int i, j;
   int size1 = mid - lb + 1;
   int size2 = ub - mid;

    M* tmpArray1 = new M[size1 + 1];
    M* tmpArray2 = new M[size2 + 1];

    for( i=0; i<size1; i++ )
    {
        tmpArray1[i] = list[lb + i - 1];
    }

    for( j=0; j<size2; j++ )
    {
        tmpArray2[j] = list[mid + j];
    }

    tmpArray1[size1 + 1] = INT_MAX;
    tmpArray2[size2 + 1] = INT_MAX;

    i = 0;
    j = i;

    for( int k=lb; k<ub; k++ )
    {
        if ( tmpArray1[i] <= tmpArray2[j] )
        {
            list[k] = tmpArray1[i];
                i++;
        }
        else
        {
            list[k] = tmpArray2[j];
            j++;
        }
    }
}

それはおそらく反復問題のようなばかげたものです...何かアイデアはありますか?

4

3 に答える 3

2

mergeSortコードが正しいと仮定しています。つまりub、ソートされる範囲の最後のインデックスであるはずです。そうでない場合、mergeSortは間違って実装されています (mergeまだ実装されていますが、方法はわずかに異なります)。

移入時に範囲の前から要素にアクセスしますtmpArray1。

for( i=0; i<size1; i++ )
{
    tmpArray1[i] = list[lb + i - 1];
}

範囲の最初の要素はlist[lb]ではなくlist[lb-1]です。

データを入力するときに、範囲の末尾にある 1 つの要素を無視していますtmpArray2。

for( j=0; j<size2; j++ )
{
    tmpArray2[j] = list[mid + j];
}

そこにあるはずlist[mid + 1 + j]です。

マージするとき、すべての要素をマージし直すわけではありません:

for( int k=lb; k<ub; k++ )
{
    if ( tmpArray1[i] <= tmpArray2[j] )
    {
        list[k] = tmpArray1[i];
            i++;
    }
    else
    {
        list[k] = tmpArray2[j];
        j++;
    }
}

k <= ubそれはループ制御にあるはずです。

でも、私が一番心に引っかかるのは

tmpArray1[size1 + 1] = INT_MAX;
tmpArray2[size2 + 1] = INT_MAX;

配列に が含まれている場合INT_MAX、または要素の型がlong long.

センチネル値を使用して配列の末尾をマークするのは適切ではありません。インデックスを使用してそれを検出する必要があります。

于 2013-01-22T23:52:46.367 に答える
2

この行で：

    tmpArray1[i] = list[lb + i - 1];

確かにあなたはこれを意味します：

    tmpArray1[i] = list[lb + i];

それ以外の場合は、指定されたマージ境界の外側から 1 つの値を取得しているため、重複した数値が説明されます。リストに書き戻すときは、そのロジックを使用しません。

于 2013-01-22T23:51:19.343 に答える
1

あなたのアルゴリズムにはいくつかの問題があります。

まず第一に、決して削除しない配列を割り当てるため、メモリ リークが発生します。問題を解決するには、いくつかのdelete[]指示が必要です。

第二に、インデックス付けエラーがあります: 一部のインデックスは負にtmpArray1[i] = list[lb + i - 1];なりlbますi。

3 番目に、基本ステップがありません。2 つの要素の値を交換することはありません。再帰ステップは問題ないように見えますが、再帰は終了して、ある時点で具体的なことを行う必要があります (つまり、範囲が 2 つの要素しかない場合)。mergeSort()関数は範囲を分割し、最初と 2 番目のサブ範囲を再帰的に呼び出しますが、再帰が終了しても何もしません。

第 4 に、2 つのサブ範囲のサイズが異なる場合を正しく処理していません(1 つのサブ範囲が他のサブ範囲よりも 1 要素ずつ大きくなる可能性があります)。

コードを修正する方法は次のとおりです (GCC 4.7.2 でテスト済み)。

template <class M>
void myMerge( M arr[], int lb, int mid, int ub )
{
   int i, j;
   int size1 = mid - lb + 1;
   int size2 = ub - mid;

    M* tmpArray1 = new M[size1];
    M* tmpArray2 = new M[size2];

    for( i=0; i<size1; i++ )
    {
        tmpArray1[i] = arr[lb + i]; // THIS NEEDED FIXING
    }

    for( j=0; j<size2; j++ )
    {
        tmpArray2[j] = arr[mid + 1 + j]; // THIS NEEDED FIXING AS WELL (add +1...)
    }

    i = 0;
    j = i;

    for( int k=lb; k<=ub; k++ )
    {
        if (i == size1) // HANDLES THE CASE WHEN FIRST RANGE IS SMALLER
        {
            arr[k] = tmpArray2[j];
            j++;
        }
        else if (j == size2) // HANDLES THE CASE WHEN SECOND RANGE IS SMALLER
        {
            arr[k] = tmpArray1[i];
            i++;
        }
        else if ( tmpArray1[i] < tmpArray2[j] )
        {
            arr[k] = tmpArray1[i];
            i++;
        }
        else
        {
            arr[k] = tmpArray2[j];
            j++;
        }
    }

    delete[] tmpArray1; // IMPORTANT! DON'T FORGET TO RELEASE
    delete[] tmpArray2; // THE MEMORY YOU ALLOCATE...
}

void mergeSort( int arr[], int lb, int ub )
{
    if (ub - lb > 1)
    {
        int mid = (lb + ub) /  2;
        mergeSort(arr, lb, mid);
        mergeSort(arr, mid + 1, ub);
        myMerge(arr, lb, mid, ub);
    } 
    else // DON'T FORGET TO ADD YOUR BASE STEP! (sort a trivial range of 2 elements)
    {
        if (arr[ub] < arr[lb])
        {
            int tmp = arr[ub];
            arr[ub] = arr[lb];
            arr[lb] = tmp;
        }
    }
}

// SOME TESTING...

#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main()
{
    int numbers[] = { 8, 40, 1, 5, 0, 9, 6, 4, 3, -1, 5 };
    mergeSort(numbers, 0, 10);
    copy(begin(numbers), end(numbers), ostream_iterator<int>(cout, " "));
}
于 2013-01-23T00:21:32.967 に答える