Move Fast

병합 알고리즘 (Merging Algorithm)

• 이미 정렬된 상태에서 수행하며, 병합 후에도 정렬된 상태를 유지.

• 비교자 함수를 써서 별도의 비교 연산을 구현 할 수 있음.

• merge 주어진 두 개의 범위를 하나로 합침.

  • 시간 복잡도: O(N1 + N2), 주어진 두 범위의 크기 각각 N1, N2

// until C++20
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
                OutputIt d_first );

template< class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
                OutputIt d_first, Compare comp );

// since C++20
template< class InputIt1, class InputIt2, class OutputIt >
constexpr OutputIt merge( InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first );

template< class InputIt1, class InputIt2, class OutputIt, class Compare>
constexpr OutputIt merge( InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2,
                          OutputIt d_first, Compare comp );

// since C++17
template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                  ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare>
ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                  ForwardIt2 first2, ForwardIt2 last2,
                  ForwardIt3 d_first, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <random>
#include <functional>
using namespace std;

int main() {
    // fill the vectors with random numbers
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<> dis(0, 9);

    vector<int> v1(10), v2(10);
    generate(v1.begin(), v1.end(), bind(dis, ref(mt)));
    generate(v2.begin(), v2.end(), bind(dis, ref(mt)));

    // sort
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    // output v1
    cout << "v1 : ";
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // output v2
    cout << "v2 : ";
    copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // merge
    cout << "After merging" << endl;
    vector<int> dst;
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(dst));

    // output
    cout << "dst: ";
    copy(dst.begin(), dst.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
v1 : 0 1 1 1 3 4 7 7 7 8
v2 : 0 1 2 2 3 4 5 5 8 9
After merging
dst: 0 0 1 1 1 1 2 2 3 3 4 4 5 5 7 7 7 8 8 9
$ ./a.out
v1 : 0 0 2 4 5 6 7 9 9 9
v2 : 0 2 4 4 4 5 5 6 7 7
After merging
dst: 0 0 0 2 2 4 4 4 4 5 5 5 6 6 7 7 7 9 9 9
 */

• inplace_merge 메모리를 추가로 사용하지 않고 주어진 두 범위를 하나로 합침.

  • 시간 복잡도: O(N * log(N)), 합쳐진 범위의 크기 = N

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

template< class BidirIt, class Compare>
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class BidirIt >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last );

template< class ExecutionPolicy, class BidirIt, class Compare>
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template<class Iter>
void merge_sort(Iter first, Iter last) {
    if (last - first > 1) {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        inplace_merge(first, middle, last);
    }
}

int main() {
    vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for(auto n : v) cout << n << ' ';
    cout << endl;

    vector<int> v2{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    inplace_merge(v2.begin(), v2.begin() + (v2.end() - v2.begin()) / 2, v2.end());
    for(auto n : v2) cout << n << ' ';
    cout << endl;
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
-2 0 1 2 3 7 8 11 11
1 2 3 4 5 6 7 8 9 10
 */