0

次のマージソート関数を使用して配列をソートしようとしています。ただし、期待される出力が得られません。正しい/期待される出力が出力されません。

入力: 5,4,3,2,1
出力: 1,2,3,4,5

代わりに、2,3,4,5,1,9,8,7,8,4,1,8,8,2 が得られます。

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;

void mergeSort(int a[], int low , int high,int res[]);
void merge(int a[], int low , int mid , int high,int res[]);
void mergeSort(int numbers[], int temp[], int array_size);

const int SIZE=5;

int main () {

    int sorted[SIZE];
    for (int i=0; i<SIZE; i++) {
        cout << "input numbers" <<endl;
        cin >>sorted[i];
    }
    int merge[SIZE];

    mergeSort(sorted,merge,SIZE);

    for (int i=0; i<SIZE; i++) {
        cout << merge[i];
    }

    return 0;
}

void mergeSort(int numbers[], int temp[], int array_size)
{
    mergeSort(numbers, 0, array_size-1, temp);
}

void mergeSort(int a[], int low , int high,int res[])
{
    int mid = (low + high)  /2;
    if (low + 1 < high)
    {
        //  Sort sub-parts
        mergeSort(a,low,mid,res);
        mergeSort(a,mid,high,res);

        //  Merge back to "res"
        merge(a,low,mid,high,res);
    }else{
        res[low] = a[low];
    }
}

void merge(int a[], int low , int mid , int high,int res[])
{
    int i = low;
    int j = mid;
    int k = low;   //  Use "low" instead of 0.

    while (i < mid && j < high)
        if(a[i] < a[j])
            res[k++] = a[i++];
        else
            res[k++] = a[j++];

    while (i < mid)
        res[k++] = a[i++];

    while (j < high)
        res[k++] =a[j++];

    //  Copy back to "a"
    for (int c = low; c < high; c++){
        a[c] = res[c];
    }
}
4

3 に答える 3

3

これが問題を引き起こしていると思います -

    //  Sort sub-parts
    mergeSort(a,low,mid,res);
    mergeSort(a,mid,high,res);

そのはず

    //  Sort sub-parts
    mergeSort(a,low,mid,res);
    mergeSort(a,mid+1,high,res);

またif (low + 1 < high)、に変更する必要がありますif (low < high)

さらに、その下の単一の while ループも <= で更新する必要がありwhile (i < mid && j < high)ますwhile (i <= mid && j <= high)

于 2013-10-18T05:16:38.300 に答える
1

インデックス作成の制限の扱いには少し混乱があります。

範囲を表す 2 つの非常に一般的な方法は次のとおりです。

  1. 範囲制限は要素間を指しています
  2. 範囲制限は要素を指しています

範囲座標系

上の図では、番号付けは「要素間を指す」アプローチを使用しており、グレー表示されている範囲は(2, 5)です。

以下の番号付けは、代わりに「要素を指す」アプローチを使用しており、同じ範囲は(2, 4).

個人的な好みとして、私は「要素間」のアプローチがはるかに好きです。たとえば、範囲のサイズは であり、high-low空の範囲や逆の範囲を簡単に表すことができます。ただし重要なことは、範囲を管理するコードを作成するときに最初または 2 番目のアプローチを使用している場合、常に頭の中で明確にしておくことです。

あなたのコードには、そのような混乱があります。たとえば、mergesortチェックしている場合

low + 1 < high

これは、「要素間」アプローチを使用していることを意味します。 whenhigh - low = 1は要素が 1 つしかなく、並べ替えが不要であることを意味するためです。また、再帰的な受け渡し(low, mid)と: 2 回(mid, high)移動したくないため、「要素間」アプローチが使用されていることを示す別の明確な兆候です。array[mid]

0ただし、同じコードでは関数を渡していますがarray_size-1、メインプログラムでは、この場合は代わりに「要素を指す」アプローチを使用していることを明確に示しています。

すべてのインデックスと範囲の使用法が一貫しており、コードが問題ないことを再確認してください。

于 2013-10-18T06:21:25.357 に答える
0

サンプルコードによると、結果として出力される数値は5つだけです( const int SIZE=5のため)。

それはさておき、リストの最後の要素の位置を「高」パラメーターとして指定することに注意してください。

ただし、マージ関数では、while(j < high)条件により、リストの最後の要素がソートされないことが保証されます。これは、ソートがそれに到達する直前に停止するためです。

更新: マージ関数の最後の for ループは、最後の ("high") 要素も配列aにコピーして戻すように調整する必要があります。

于 2013-10-18T05:14:45.390 に答える