[알고리즘] Merge Sort (합병 정렬) 구현 (C++)

(공부한 곳 출처: https://velog.io/@codenmh0822/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC)

Merge Sort란 분할 정복의 방법을 차용한 방식으로 어떠한 경우에도 시간 복잡도가 O(nlogn)이 나오는 정렬 알고리즘이다.

1. 크기가 1인 배열이 될 때까지 분할한다.
2. 왼쪽 오른쪽으로 분할된 배열을 합치면서(merge) 정렬한다.

시간 복잡도가 O(nlogn)이 나오는 이유는 원소의 개수가 n인 배열을 트리화(?)시키면 무조건 높이는 logn이 된다는 사실을 안다.

+병합하는 단계에서 리커시브 콜의 길이를 생각해보면 된다.

분할하는 단계는 시간 복잡도로 치지 않는다.

그리고, 각각의 단계(각각의 리커시브 콜 모음)에서 최대 n번의 비교 연산이 일어나므로 O(n * logn)으로

>> O(nlogn)이 되는 것이다.

 

+다른 정렬과 달리 정렬이 된 배열을 따로 선언해줄 필요가 있었다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> v;

vector<int> merge(vector<int> left, vector<int> right){
    vector<int> sortingArr;
    
    int leftIdx = 0;
    int rightIdx = 0;
    
    // left와 right에서 작은 원소들 부터 push
    while(leftIdx < left.size() && rightIdx < right.size()){
        if(left[leftIdx] < right[rightIdx]){
            sortingArr.push_back(left[leftIdx]);
            leftIdx++;
        }
        else{
            sortingArr.push_back(right[rightIdx]);
            rightIdx++;
        }
    }
    
    // 남은 원소들 마저 push 해주어야 함.
    if(leftIdx == left.size()){
        while(rightIdx < right.size()){
            sortingArr.push_back(right[rightIdx]);
            rightIdx++;
        }
    }
    else{
        while(leftIdx < left.size()){
            sortingArr.push_back(left[leftIdx]);
            leftIdx++;
        }
    }
    
    /*
    cout << "merge..." << '\n';
    for(int i = 0; i < sortingArr.size(); i++){
        cout << sortingArr[i] << ' ';
    }
    cout << '\n';
    */
    
    
    return sortingArr;
}

vector<int> mergeSort(vector<int> arr){
    if(arr.size() < 2) return arr;
    
    int mid = arr.size() / 2;
    
    vector<int> left;
    vector<int> right;
    
    // 벡터 복사 관련 메서드 없나?
    for(int i = 0; i < mid; i++){
        left.push_back(arr[i]);
    }
    for(int i = mid; i < arr.size(); i++){
        right.push_back(arr[i]);
    }
    
    /*
    cout << '\n';
    cout << "sorting..." << '\n';
    for(int i = 0; i < left.size(); i++){
        cout << left[i] << ' ';
    }
    for(int i = 0; i < right.size(); i++){
        cout << right[i] << ' ';
    }
    cout << '\n';
    */
    
    return merge(mergeSort(left), mergeSort(right));
}

int main(){
    
    // 배열에 8 ~ 1 내림차순으로 push
    for(int i = 8; i >= 1; i--){
        v.push_back(i);
    }
    
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ' ';
    }
    
    vector<int> sorted = mergeSort(v);
    
    cout << '\n';
    // 정렬된 배열 출력
    for(int i = 0; i < sorted.size(); i++){
        cout << sorted[i] << ' ';
    }
    return 0;
}

[vector.ver]

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> v(100001, 0);

vector<int> merge(vector<int> leftArr, vector<int> rightArr){
    vector<int> sorted;
    
    int leftIdx = 0, rightIdx = 0;
    
    while(leftIdx < leftArr.size() && rightIdx < rightArr.size()){
        if(leftArr[leftIdx] < rightArr[rightIdx]){
            sorted.push_back(leftArr[leftIdx]);
            leftIdx++;
        }
        else{
            sorted.push_back(rightArr[rightIdx]);
            rightIdx++;
        }
    }
    
    if(leftIdx == leftArr.size()){
        while(rightIdx < rightArr.size()){
            sorted.push_back(rightArr[rightIdx]);
            rightIdx++;
        }
    }
    else{
        while(leftIdx < leftArr.size()){
            sorted.push_back(leftArr[leftIdx]);
            leftIdx++;
        }
    }
    
    return sorted;
}

vector<int> mergeSort(vector<int> arr, int size){
    if(size < 2) return arr;
    
    int mid = size / 2;
    
    vector<int> leftArr;
    vector<int> rightArr;
    
    for(int i = 0; i < mid; i++){
        leftArr.push_back(arr[i]);
    }
    for(int i = mid; i < size; i++){
        rightArr.push_back(arr[i]);
    }
    
    return merge(mergeSort(leftArr, mid), mergeSort(rightArr, size - mid));
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    
    vector<int> mergeSortTree = mergeSort(v, n);
    
    cout << mergeSortTree.size() << '\n';
    for(int i = 0; i < n; i++){
        cout << mergeSortTree[i] << ' ';
    }
    
}