Merge Sort (build) - 2751 C++

문제

---

백준 2751번

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

 

개요

---

기본적인 정렬 문제이나 범위가 상당하다. 만약 O(n²) 시간복잡도의 코드를 짜게된다면 반드시 시간 초과가 뜰 것이다.

이런 경우 복잡한 문제가 아니기 때문에 많은 사람들은 <algorithm> 헤더의 sorted 함수를 이용할 것 이다.

허나 나는 기본제공되는 함수를 이용하는 것이 아니라 직접 코드를 짤 것이다.

 

 

먼저 ,

어떤 정렬 알고리즘을 이용할지 정해야한다. 떠오르는 건

1.선택정렬  2.삽입정렬  3.버블정렬  4.병합정렬  5.힙정렬  6.퀵정렬

이 중 우리가 사용할 수 있는 알고리즘은 병합정렬과 힙정렬, 그리고 내가 사용할 건 병합정렬(MergeSort)이다.

(퀵정렬은 평균은 O(nlogn)이지만 최악의 경우 O(n²)이므로 사용하지 않는다.)

 

 

---

개념

---

병합정렬은 기본적으로 분할정복(Divide and Conquer) 개념을 이용한다. 

분할정복 : 하나의 문제를 작은 두개의 문제로 나누고 각각 해결한 후 모아서 원래의 문제를 해결하는 방식

{대게 순환 호출(재귀함수)을 이용}

 또한, 메모리 공간만큼의 추가 공간이 필요하므로 제자리 정렬이 아니다

 

 

과정

---

1. merge_sort 함수를 호출 함으로써 정렬하고자 하는 list를 왼쪽과 오른쪽으로 나눔.

2. merge_sort를 재귀적으로 호출해서 나눌 수 있는 최소 단위까지 나눠줌.

3. list의 길이가 0과 1일 경우엔 정렬이 되어있다고 판단하고 merge함수를 이용해 왼쪽과 오른쪽으로 나눠진 리스트를 병합

4.정렬된 sorted 배열의 값을 다시 arr배열에 넣으면서 마무리

 

분할, 병합

 

병합의 자세한 과정

 

 

코드

---

#include <iostream>
using namespace std;

void merge(int* arr, int* sorted, int first, int end, int mid){ //리스트 왼쪽 오른쪽 정렬 함수
    int i = first;
    int k = mid+1; 
    int j = first; //sorted 배열의 포인터 역할

    //first ~ mid => 왼쪽 리스트, mid+1 ~ end => 오른쪽 리스트

    while(i <= mid && k <= end){
        if(arr[i] < arr[k]){
            sorted[j] = arr[i];
            i++;
        }
        else{
            sorted[j] = arr[k];
            k++;
        }
        j++;
    }
    // 잔여 인덱스 정렬하는 과정
     if(i>mid){ 
        for(int x=k; x<=end; x++){
            sorted[j]=arr[x];
            j++;
        }
    }
    else{
        for(int x=i; x<=mid; x++){
            sorted[j]=arr[x];
            j++;
        }
    }

    for(int l= first; l <=end; l++){
        arr[l]=sorted[l]; //정렬된 리스트로 값 바꾸기
    }
}

void merge_sort(int* arr, int* sorted, int first, int end){
    if(first < end){
        int mid = (first + end)/2;
        merge_sort(arr, sorted, first, mid); //리스트 분할 (왼쪽)
        merge_sort(arr, sorted, mid+1, end); //리스트 분할 (오른쪽)
        merge(arr, sorted, first, end, mid); //현재 리스트 병합하기 위한 호출
    }
}


int main(){
    int N, num;
    cin >> N;
    int* arr = new int[N]; 
    int* sorted = new int[N]; //정렬 시키기 위해 잠시 쓰는 리스트

    for(int i =0; i<N; i++){
        cin >> arr[i];
    }
    merge_sort(arr, sorted, 0, N-1);
    
    for(int i =0; i <N; i++){
        cout << arr[i] <<'\n';
    }

    delete[] arr;
    delete[] sorted;
    return 0;
}

N의 최댓값이 1,000,000 으로 정해져 있기 때문에 크기가 1,000,000인 배열을 만들어서 해결해도 상관없다.

 

 

 

 

참고 및 이미지 출처

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

https://www.geeksforgeeks.org/merge-sort/