[STL] merge

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

/*   merge 알고리즘은 두 개의 정렬된 구간을 머지하여 이 두 입력 구간과 겹치지 않는 구간에 출력 결과를 집어넣는다. inplace_merge 알고리즘은 두 개의 연속된 정렬 구간을 머지하며, 머지한 결과는 이 두 구간을 대체한다.   merge 알고리즘의 시간 복잡도는 선형적이다. inplace_merge의 시간 복잡도는 추가로 확보할 수 있는 메모리 공간의 양에 따라 좌우된다. 메모리를 추가로 확보할 수 없는 경우에는 소요 시간이 O(N log N)이며, 그렇지 않은 경우 선형적이다.   */     #include <iostream> #include <cassert> #include <algorithm> #include <vector>   using namespace std;   int main() {     cout<< "Illustrating the generic merge algorithms."<< endl;     // 정수의 벡터를 초기화     vector<int> vector1(5);     vector<int> vector2(5);     vector<int> vector3(10);       int i;     for (i=0; i< 5; ++i)         vector1[i] = 2*i;           // 짝수 : 0 2 4 6 8       for (i=0; i< 5; ++i)         vector2[i] = 1+ 2*i;        // 홀수 : 1 3 5 7 9       // vector1과 vector2를 머지하여 vector3를 만들어낸다.     merge(vector1.begin(), vector1.end(),           vector2.begin(), vector2.end(),           vector3.begin());       for (i=0; i< 10; ++i)         assert (vector3[i] == i);       for (i=0; i< 5; ++i)         vector3[i] = vector1[i];        for (i=0; i< 5; ++i)         vector3[i+5] = vector2[i];       cout<< "Before inplace_merge :\n";     copy(vector3.begin(), vector3.end(), ostream_iterator<int>(cout, " "));     cout<< endl;         // 반씩 정렬된 두 부분을 vector3 내에서 머지하여     // 정렬된 vector3를 얻는다.     inplace_merge(vector3.begin(), vector3.begin()+5,                   vector3.end());       cout<< "After inplace_merge :\n";     copy(vector3.begin(), vector3.end(), ostream_iterator<int>(cout, " "));     cout<< endl;         for (i=0; i< 10; ++i)         assert (vector3[i] == i);     cout<< " --- Ok."<< endl;       return 0; }