c++ - マージソートの実装

Question

私はC ++が初めてで、マージソートのコードを開発しようとしていました. サイズ 5 のサンプル配列でテストしましたが、コードによって出力された答えは正しくありません。何が問題なのかわかりません。これが私のコードです：

#include <iostream>
#include <cstring>
#include <sstream>
#include <fstream>
#include <iomanip>
using namespace std;
void merge(int, int, int, int*);
void merge_sort(int low, int high, int* p){
    int pivot;
    static int i(1);
    if (high>low)
    {
        cout << "calling merge_sort: "<<i<<endl; i++;
        pivot = low + ((high - low)/2);
        cout << pivot << endl;
        merge_sort(low, pivot, p);
        merge_sort(pivot+1, high, p);
        merge(low, pivot, high, p);

    }
}
void merge(int l, int pi, int h,int* arr)
{
            int start = l;
        int mid = pi+1;
        while((start<=pi)&&(mid <=h)){
            if (arr[start] > arr[mid])
            {
                int temp = arr[mid];
                arr[mid] = arr[start];
                arr[start] = temp;
                mid++;
             }
            else
                start++;
    }
}
int main() 
{
    int a[] = {2, 42, 3, 7, 1};
    merge_sort(0, 4, a);
    for (int i = 0; i<=4 ; i++)
        cout << a[i] << endl;
    return (0);

}

出力は次のとおりです。

calling merge_sort: 1
2
calling merge_sort: 2
1
calling merge_sort: 3
0
calling merge_sort: 4
3
1
3
7
2
42

stackoverflow でのマージソート実装のコードを見たことがありますが、それらは別の一時配列を使用しているため、これは避けたいと考えています。

この問題を分類する上で、どんな助けも大歓迎です。

score 3 · Accepted Answer

マージのロジックが間違っています。マージフェーズ中に、並べ替えられた数値のセクションが 2 つあることがわかります。比較して交換するとarr[start]、arr[mid]の場合、数値の一番上のセットの並べ替えが壊れますarr[start] > arr[mid+1]。この例は、2 が間違った場所に残されるため、コードの問題を示しています。

4 6 8 | 1 3 5  ->  1 6 8 | 4 3 5
^       ^          ^         ^

2 つのセクションを並べ替えたままにするarr[start]には、数字の一番上のセットの正しい場所に挿入する必要があり、複雑さがよりも悪くなりO(n lg n)ます。これが、2 番目の配列が使用される理由です。

マージに元の配列よりも小さい配列を使用する方法があります。これらにはオーバーヘッドがありますが、複雑さ (または正確さ) は損なわれません。インプレースソートが必要な場合O(n lg n)は、クイックソートまたはヒープソートが最適です。

score 2 · Accepted Answer

以下は、整数配列のマージソートの実装です。

void merge_sort (int array[], int size)
{
    int temp[size];
    int mid, i;
    if (size < 2) {
        return;
    } 
    else {
        mid = size / 2;
        merge_sort(array, mid);
        merge_sort(array + mid, size - mid);
        merge (array, mid, array + mid, size - mid, temp);
        for (i = 0; i < size; i++) {
            array[i] = temp[i];
        }
    }
}

int  merge  (int list1[ ] , int size1 , int list2[ ] , int size2 , int list3[ ])
{
    int i1, i2, i3;
    if (size1+size2 > size) {
        return false;
    }
    i1 = 0; i2 = 0; i3 = 0;
    /* while both lists are non-empty */
    while (i1 < size1 && i2 < size2) {
        if (list1[i1] < list2[i2]) {
            list3[i3++] = list1[i1++];
        } 
        else {
            list3[i3++] = list2[i2++];
        }
    }
    while (i1 < size1) {   
        /* copy remainder of list1 */
        list3[i3++] = list1[i1++];
    }
    while (i2 < size2) { 
        /* copy remainder of list2 */
        list3[i3++] = list2[i2++];
    }
    return true;
}

他のタイプに使用したい場合は、次のように C++ テンプレートで使用できます。

    template <class T>
T* merge_sort(T arr[], int n)
{
    if(n < 2){return arr;}
    int mid = n/2;
    T *arr1 = merge_sort<T>(arr,mid);
    T *arr2 = merge_sort<T>(arr+mid,n-mid); 
    return merge(arr1, mid, arr2, n-mid);
}

template <class T>
T* merge(T arr1[], int size1, T arr2[], int size2)
{
    int i = 0,j = 0;

    T* out_array = new T[size1+size2];

    while((i < size1) && (j < size2))
    {
        if(arr1[i] >= arr2[j])
        {
            out_array[i+j] = arr2[j];
            ++j;
        }
        else
        {
            out_array[i+j] = arr1[i];
            ++i;
        } 
    }
    while(i < size1)
    {
        //copy the reminder
        out_array[i+j] = arr1[i];
        i++;
    }
    while( j < size2)
    {
        out_array[i+j] = arr2[j];
        j++;
    }
    return out_array;
}

ただし、次の場合:

 #include <iostream>
using namespace std;

int main() {
    int a[] = {2, 42, 3, 7, 1};
     int *a2 = merge_sort(a,5);
    for (int i = 0; i<= 4 ; ++i)
        cout << a2[i] << endl;
    return (0);
}

出力：

少しお役に立てば幸いです。

score 1 · Accepted Answer

これらの行は私には間違っているようです:

int temp = arr[mid-1]; // It should be [mid] here
arr[mid] = arr[start]; // Or [mid-1] here
arr[start] = temp;

2 つのインデックスを交換するには、その 2 つが一致する必要があります。

c++ - マージソートの実装

5 に答える 5

Related

Reference