Merge Sorted Array

• Reference
• 보통 두 Array를 합칠 때, 사용하는 알고리즘으로 각각의 Array에 Pointer를 두고 비교하여 새로운 Array에 써주는 식으로 Return 하는 방식이 있다. 하지만, 그렇지 않고 원래의 Array에 쓰도록 하는 문제가 이 문제다.
• 이 문제에서는 애초에 하나의 Array에 쓸 수 있는 공간을 준다.
• 두 Array가 정렬되어다는 가정하에 사용한다.

Algorithm

num1

[1, 3, 5, 0, 0, 0] m = 3

num2

[2, 4, 8] n = 3

이러한 Input이 주어지면 두 Array를 가리키는 pointers, 써내려갈 위치의 pointer를 두면 된다.

num1

[1, 3, 5, 0, 0, 0] m = 3
       p1       p3
 
num2

[2, 4, 8] n = 3
       p2

• p1, p2가 비교해서 큰 값을 p3에 쓰고, p1의 값이 클경우에는 p1, p3를 p2의 값이 클경우에는 p2, p3를하나씩 감소하면된다.
  • p1, p2 : read Pointer
  • p3 : write Pointer
• 위 알고리즘을 사용하면, Time Complexity는 O(n+m), Space Complexity는 복사하는 것이 없으므로 O(1)이 된다.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

void merge(std::vector<int> &v1, int m, std::vector<int> &v2, int n)
{
    int idx1 = m - 1;
    int idx2 = n - 1;
    int idx3 = v1.size() - 1;

    if (v2.size() <= 0)
        return;

    while (idx1 >= 0 && idx2 >= 0)
    {
        if (v1[idx1] >= v2[idx2])
        {
            v1[idx3] = v1[idx1];
            --idx1;
        }
        else
        {
            v1[idx3] = v2[idx2];
            --idx2;
        }

        --idx3;
    }

    if (idx2 >= 0)
        std::copy(v2.begin(), v2.begin() + idx2 + 1, v1.begin());
}

int main()
{
    std::vector<int> v1 = {1, 3, 5, 0, 0, 0};
    std::vector<int> v2 = {2, 4, 8};

    // std::vector<int> v1 = {4, 5, 6, 0, 0, 0};
    // std::vector<int> v2 = {1, 2, 3};

    merge(v1, 3, v2, 3);

    for (int e : v1)
        std::cout << e << ", ";

    std::cout << std::endl;

    return 0;
}

1, 2, 3, 4, 5, 8

int main()
{
    std::vector<int> v1 = {1, 3, 5, 0, 0, 0};
    std::vector<int> v2 = {2, 4, 8};

    // std::vector<int> v1 = {4, 5, 6, 0, 0, 0};
    // std::vector<int> v2 = {1, 2, 3};

    merge(v1, 3, v2, 3);

    for (int e : v1)
        std::cout << e << ", ";

    std::cout << std::endl;

    return 0;
}

1, 2, 3, 4, 5, 6

• 위의 Case 경우 v1의 값만 사용되므로 if (idx2>=0)에서 걸리게 되면서 memory copy를 수행하게 된다.