62. 병합정렬

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

8

7 6 3 1 5 2 4 8

 

출력예제 1

1 2 3 4 5 6 7 8

 

풀이 

- 왼쪽 끝과 오른쪽 끝을 lt, rt로, 그 둘을 절반한 것을 mid로 놓는다

- lt~mid까지 한 묶음 / mid+1~rt까지 한 묶음이 된다

- data[p1]과 data[p2]를 비교해서 작은 값을 tmp[p3]에 넣는다

- 이 작업을 모두 수행하면 왼쪽 묶음이든 오른쪽 묶음이든 한쪽은 tmp에 모두 들어간다

- 남은 한쪽을 넣어주기 위해 while문을 사용한다

- 모든 작업을 마친후 tmp에 있는 모든 값을 data에 옮겨 준다

- n개 데이터를 각 레벨별로 n번 비교 => nlogn

 

#include <stdio.h>
#include <algorithm>
using namespace std;
int data[10],tmp[10];

//62. 병합 정렬
void divide(int lt, int rt){
    int mid;
    int p1, p2, p3;
    if(lt<rt){
        mid=(lt+rt)/2;
        divide(lt, mid);
        divide(mid+1, rt);
        p1=lt;
        p2=mid+1;
        p3=lt;
        while(p1<=mid && p2<=rt){
            if(data[p1]<data[p2]){
                tmp[p3++]=data[p1++];
            }else{
                tmp[p3++]=data[p2++];
            }
        }
        while(p1<=mid) tmp[p3++]=data[p1++];;
        while(p2<=rt) tmp[p3++]=data[p2++];
        for(int i=lt;i<=rt;i++){
            data[i]=tmp[i];
        }
    }
}


int main(){
    int n, i;
    scanf("%d",&n); //배열 개수
    for(i=1;i<=n;i++){
        scanf("%d", &data[i]);
    }
    divide(1,n);
    for(i=1;i<=n;i++){
        printf("%d ", data[i]);
    }
    return 0;
}