

マージソートを行うプログラムを作りましたが、手を加えたはずの配列が何も変わらず帰ってきてしまいます。いろいろ調べた結果、mergeで並びを変えたはずの配列がrecMergeSortに戻ってくると変更前に戻ってしまっていました。配列の受けわたしがうまくいっていないのが原因だと思われますが、どこが間違っているのかがわかりません。

**main.cpp**

[code]

    #include <iostream>
    #include "recFunc.h"
    
    using namespace std;
    
    
    
    int main() {
    
        const int NUM_VALUES = 8;
    
        int mergeArray[NUM_VALUES] = {6, 3, 5, 1, 8, 2, 4, 8};
    
        // show starting array
        cout << "Starting array is " << endl;
        for(int i = 0; i < NUM_VALUES; i++)
            cout << mergeArray[i] << " ";
        cout << endl;
    
        // now sort it
        mergeSort(mergeArray, NUM_VALUES);
    
        // show updated array, should be in ascending order
        cout << "Now the array should be sorted" << endl;
        cout << " expected: 1 2 3 4 5 6 7 8" << endl;
        cout << " actually: ";
        for(int i = 0; i < NUM_VALUES; i++)
            cout << mergeArray[i] << " ";
        cout << endl;
    
        cout << endl << "Done with testing merge sort" << endl << endl;
        return 0;
    }
    
[/code]

**recFunc.cpp**

[code]

    #include <iostream>
    #include "recFunc.h"
    
    void mergeSort(int* array, int size)
    {
        recMergeSort(array, size);
    }
    
    void recMergeSort(int* array, int size)
    {
        if(size <= 1)
        {
            return;
        }
    
        int middle = (size - 1) / 2;
        int* arrayLeft = new int [middle+1];
        int* arrayRight = new int [(size-1)-middle];
        for(int i = 0; i < middle+1; i++)
        {
            arrayLeft[i] = array[i];
        }
        for(int i = 0; i < (size-1)-middle; i++)
        {
            arrayRight[i] = array[(middle+1)+i];
        }
    
        recMergeSort(arrayLeft, middle+1);
    
        recMergeSort(arrayRight, (size-1)-middle);
    
        int* temp = merge(arrayLeft, middle+1, arrayRight, (size-1)-middle);
    
        array = temp;
    
    }
    
    int* merge(int* arrayLeft, int leftSize, int* arrayRight, int rightSize)
    {
        int left = 0;
        int right = 0;
        int leftEnd = leftSize-1;
        int rightEnd = rightSize -1;
    
        int* temp = new int [leftSize+rightSize];
    
        while(left <= leftEnd && right <= rightEnd)
        {
            //if left value is smaller, save the value to temp
            if(arrayLeft[left] <= arrayRight[right])
            {
                temp[left+right] = arrayLeft[left];
                left++;
            }
                //otherwise(right value is smaller), save it
            else
            {
                temp[left+right] = arrayRight[right];
                right++;
            }
        }
    
        while(left <= leftEnd)
        {
            temp[left+right] = arrayLeft[left];
            left++;
        }
        while(right <= rightEnd)
        {
            temp[left+right] = arrayRight[right];
            right++;
        }
    
    
    
        return temp;
    }
    
[/code]

**recFunc.h**

[code]

    int* merge(int* arrayLeft, int leftSize, int* arrayRight, int rightSize);
    void recMergeSort(int* array, int size);
    void mergeSort(int* array, int size);
    
[/code]


CC BY-SA 4.0
2021-11-11T08:43:43.020
83563
2021-11-11T09:17:42.317
45177
question
c++
マージソートを行うプログラムを作ったが、手を加えたはずの配列が何も変わらず帰ってきてしまう。

[code]

    void recMergeSort(int* array, int size)
    {
        ...
        array = temp;
    
[/code]

引数 `array` を変更しても、`array` が指す配列は変更されません。`temp` の内容を1要素ずつ `array`
が指す先にコピーするか、`merge()` 関数に書き込み先として `array` を渡すとよさそうです。


CC BY-SA 4.0
2021-11-11T09:17:42.317
83565
2021-11-11T09:17:42.317
3475
83563
answer