baekjoon 1181 w/ mergesort

#include<stdio.h>
#include<string.h>

typedef struct{
    char string[51];
    int length;
} str;

str order[20000];
void mergesort(str*,int,int);
void merge(str*,int,int,int);

int main(){
    int N;
    scanf("%d", &N);
    str arr[N];
    for(int i=0;i<N;i++){
        scanf("%s", arr[i].string);
        arr[i].length = strlen(arr[i].string);
    }
    mergesort(arr,0,N-1);
    
    puts(arr[0].string);
    for(int i=1;i<N;i++){
        if(strcmp(arr[i].string,arr[i-1].string)!=0)
            puts(arr[i].string);
    }
    
    return 0;
    
}

void merge(str* arr, int first, int mid, int last){
    int i = first; //i와j는 두개의 sub arr를 비교할때 쓰고,
    int j = mid + 1; // k는 order에 쭉 정렬할때 사용됨.
    int k = first;
    
    while(i<=mid && j<=last){
        if(arr[i].length<arr[j].length)
            order[k++] = arr[i++];
        else if(arr[i].length>arr[j].length)
            order[k++] = arr[j++];
        else{
            if(strcmp(arr[i].string,arr[j].string)>0)
                order[k++] = arr[j++];
            else
                order[k++] = arr[i++];
        }
    }
    while(i<=mid)
        order[k++] = arr[i++];
    while(j<=last)
        order[k++] = arr[j++];
        
    for(int i=first;i<=last;i++)
        arr[i] = order[i];
}

void mergesort(str* arr, int first, int last){
    int mid = (first + last) / 2;
    if(first<last){
        mergesort(arr,first,mid);
        mergesort(arr,mid+1,last);
        merge(arr,first,mid,last);
    }
}

 

결국 핵심은 하나의 배열을 계속 두개로 분리하고, 두 배열을 새로운 하나의 배열에 정렬하여 합체. 두 배열의 원소의 합이 n개이면

하나로 합치면서 정렬시킬때 총 n의 비교가 발생. N을 결국 하나의 배열에 하나의 원소만 들어갈때까지 반띵하므로 logn 총 O(nlogn)의 시간복잡도가 발생함.

 

 

 

더 자세한 설명은 https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html 에서 퍼왔음.

순환 호출의 깊이 (합병 단계의 수)
레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 이것을 일반화하면 n=2^k의 경우, k(k=log₂n)임을 알 수 있다.
k=log₂n
각 합병 단계의 비교 연산
크기 1인 부분 배열 2개를 합병하는 데는 최대 2번의 비교 연산이 필요하고, 부분 배열의 쌍이 4개이므로 24=8번의 비교 연산이 필요하다. 다음 단계에서는 크기 2인 부분 배열 2개를 합병하는 데 최대 4번의 비교 연산이 필요하고, 부분 배열의 쌍이 2개이므로 42=8번의 비교 연산이 필요하다. 마지막 단계에서는 크기 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하고, 부분 배열의 쌍이 1개이므로 8*1=8번의 비교 연산이 필요하다. 이것을 일반화하면 하나의 합병 단계에서는 최대 n번의 비교 연산을 수행함을 알 수 있다.
최대 n번
순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = nlog₂n
이동 횟수
순환 호출의 깊이 (합병 단계의 수)
k=log₂n
각 합병 단계의 이동 연산
임시 배열에 복사했다가 다시 가져와야 되므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생한다.
순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 이동 연산 = 2nlog₂n
T(n) = nlog₂n(비교) + 2nlog₂n(이동) = 3nlog₂n = O(nlog₂n)