합병 정렬(merge sort)

합병 정렬을 구현해 보았습니다. 

가끔 알고리즘 문제에서 STL을 사용하지 못하게하는 회사들이 간혹 있는데요, 

STL을 사용하지 못하게 한다는건 기본적으로 <algorithm> 라이브러리를 이용한 sort() 함수를 

사용하지 못한다는 뜻입니다. (그 외에 다른 구현 능력을 보는 거 일수도 있지만요....^^)

그 말은 즉, 시험 응시자에게 "너 합병정렬, 퀵 정렬, 힙정렬 이거 구현할 줄 알아?" 라고 묻는거라고 

할 수 있겠죠? 

 

물론, 정렬을 구현하는데서 끝나는 것이 아니라, 그 외에 부가적인 것을 추가로 구현해야 하겠지만

첫 번째로! 문제에서 정렬을 직접 구현하라고 했을 때, 보자모자 무릎을 탁! 치고 바로 10분안에 코딩 할 수 있는 

능력이 있어야 그 다음을 해결할 수 있겠죠?? 

 

합병 정렬의 차근차근 몇번 따라 해보면 그렇게 어렵지 않으니, 따라 구현 해보시고 스스로 보지 않고 혼사서도

구현해 보시기 바랍니다. 

 

여기서 중요한거! ( 코딩을 외우는 것도 중요하지만, 어떠한 로직으로 구현이 되어 있는지를

머릿속에 먼저 넣어두는게 더 중요하다는거 ! 절대 ! 잊지마시고 연습! 연습! 또 연습!) 

 

 

/*
합병정렬: 배열을 절반으로 나누어 각가을 정렬한 수 합친다. 
 
시간 복잡도: nlog(n)
*/
 
#include <stdio.h>
 
void merging(int arr[], int s1, int e1, int s2, int e2){
    // arr의 s1 ~ e1이 왼쪽 절반, s2 ~ e2가 오른쪽 절반일 때,
    // 이 둘을 합쳐서 arr의 s1 ~ e2를 정렬된 결과로 만드는 함수
 
    // 1 2 4 8        3 4 6 7
    // temp 배열에 정렬된 값을 넣어준다. 
 
    int p, q; // p와 q의 현재 최솟값을 가리키는 변수들
    int temp[100005]; // 합쳐진 결과를 저장하는 임시변수
    int temp_inx = 0;
 
    p = s1, q = s2;
 
    // 1 2 4 8  2 2 3 3
    // p                q
 
    while(p <= e1 && q <= e2){
 
        if(arr[p] <= arr[q]){
            temp[temp_inx++] = arr[p];
            p++;
        }
        else{
            temp[temp_inx++] = arr[q];
            q++;
        }
    }
 
    if(p > e1){
        for(int i = q; i <= e2; i++){
            temp[temp_inx++] = arr[i];
        }
    }
    else{
        for(int i = p; i <= e1; i++){
            temp[temp_inx++] = arr[i];
        }
    }
    // temp는 완성 되었으니
    // arr[s1 ~ e2] 까지에 temp의 값을 복사
    for(int i = s1; i <= e2; i++)
        arr[i] = temp[i-s1];
}
 
void mergeSort(int arr[], int start, int end){
    // arr의 start부터 end까지 합병정렬하는 함수
 
    if(start>=end) return ;
    else{
        /*
        1. 왼쪽 절반을 합병정렬
        2. 오른쪽 절반을 합병정렬
        3. 그 둘을 합친다. 
        */
        int mid = (start+end)/2;
 
 
        mergeSort(arr, start, mid);
        mergeSort(arr, mid+1, end);
 
        // arr(start ~ mid), arr[mid+1 ~ end]는 정렬이 이미 되어있음
 
        merging(arr, start, mid, mid+1, end);
    }
}
 
int main(){
 
    int n; 
    int numbers[100005];
 
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &numbers[i]);
    }
 
    mergeSort(numbers, 0, n-1);
 
    for(int i = 0; i < n; i++)
        printf("%d ", numbers[i]);
 
    return 0;
}