c++ - インプレースマージソート

Question

インプレースマージソートが機能するようになるのに少し問題があります。誰かが私が始めるのを助けることができるアルゴリズムやヒントを持っていますか？

Answer 1

mergesort.cpp

#include "mergesort.h"
#include <limits>
#include <vector>
#include <iostream>
using namespace std;

void merge_sort(int *data, int start, int end){
    if (start < end){
        int middle = int((end + start) / 2);
        merge_sort(data, start, middle);
        merge_sort(data, middle+1, end);
        merge(data, start, middle+1, end);
    }
}


void merge(int *data, int start, int middle, int end){
    int left[middle-start+1];
    for (int l_cnt=0; l_cnt<middle-start; l_cnt++){
        left[l_cnt] = data[start+l_cnt];
    }
    left[middle-start] = numeric_limits<int>::max();
    int right[end-middle+2];
    for (int r_cnt=0; r_cnt<end-middle+1; r_cnt++){
        right[r_cnt] = data[middle+r_cnt];
    }
    right[end-middle+1] = numeric_limits<int>::max();
    int i = 0;
    int j = 0;
    for (int k=start; k<=end; k++){
        if (left[i] < right[j]){
            data[k] = left[i];
            i++;
        }
        else{
            data[k] = right[j];
            j++;
        }
    }
}

mergesort.h

#ifndef INSERTIONSORT_H_
#define INSERTIONSORT_H_
void merge_sort(int *data, int start, int end);
void merge(int *data, int start, int middle, int end);
#endif

そしてユニットテストファイル

#include "mergesort.h"
#include "gtest/gtest.h"

template<typename T, size_t size>
    ::testing::AssertionResult ArraysMatch(const T (&expected)[size],
                                           const T (&actual)[size]){
        for (size_t i(0); i < size; ++i){
            if (expected[i] != actual[i]){
                return ::testing::AssertionFailure() << "array[" << i
                    << "] (" << actual[i] << ") != expected[" << i
                    << "] (" << expected[i] << ")";
            }
        }
        return ::testing::AssertionSuccess();
}

namespace{
    class MergeSortTest : public ::testing::Test{
        protected:
            MergeSortTest() {}
            virtual ~MergeSortTest() {}
            virtual void SetUp() {}
            virtual void TearDown() {}
    };

    TEST(MergeSortTest, MergeTwo){
        int raw_array[] = {6,0,5,2,4,1,9,7};
        merge(raw_array, 2, 3, 3);
        int sorted_array[] = {6,0,2,5,4,1,9,7};
        EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
    }

    TEST(MergeSortTest, MergeFive){
        int raw_array[] = {6,0,2,5,1,4,9,7};
        merge(raw_array, 2, 4, 6);
        int sorted_array[] = {6,0,1,2,4,5,9,7};
        EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
    }

    TEST(MergeSortTest, SortTwo){
        int raw_array[] = {5, 2};
        int sorted_array[] = {2, 5};
        merge_sort(raw_array, 0, 1);
        EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
    }

    TEST(MergeSortTest, SortThree){
        int raw_array[] = {5, 2, 4};
        int sorted_array[] = {2, 4, 5};
        merge_sort(raw_array, 0, 2);
        EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
    }

    TEST(MergeSortTest, Five){
        int raw_array[] = {5, 2, 4, 1, 9};
        int sorted_array[] = {1, 2, 4, 5, 9};
        merge_sort(raw_array, 0, 4);
        EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
    }
}

int main(int argc, char **argv){
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

Answer 2

インプレースマージソートとは、制限サイズのバッファを使用してマージソートを実行することです。そして、結果よりも小さいバッファで2つのソートされたリストをマージする方法になります。

STLには、インプレースマージソートが実装されています。