합병 정렬(Merge Sort)

합병 정렬(Merge Sort)은 정렬 알고리즘 중 하나로, 데이터를 빠르게 정렬하는 방법이다. 🧩 데이터를 반으로 나누고, 정렬한 후에 다시 합치는 과정이다. 구체적으로 알아보자.

1. 합병 정렬이란? 🤔

합병 정렬은 "분할 정복(Divide and Conquer)" 방법을 사용한다. 문제를 작은 문제로 나누고, 각각을 해결한 후 다시 합치는 방식이다. 이를 통해 데이터가 점점 정렬되는 구조이다.

2. 합병 정렬의 과정 🔍

• 1단계: 분할(Divide) – 데이터를 더 이상 나눌 수 없을 때까지 반으로 나눈다.
• 2단계: 정복(Conquer) – 나눠진 작은 단위에서 정렬을 시작한다.
• 3단계: 합병(Merge) – 정렬된 작은 단위들을 하나로 합쳐서 전체를 정렬된 상태로 만든다.

예시로 이해해보기 📐

예를 들어 [8, 4, 7, 3, 1, 5, 6, 2]라는 리스트가 있다고 하자.

1. 반으로 나누기: [8, 4, 7, 3]와 [1, 5, 6, 2]로 나눈다.
2. 계속 분할: [8, 4], [7, 3], [1, 5], [6, 2]로 나누고, 더 나누면 [8], [4], [7], [3] 등으로 쪼개진다.
3. 정렬 후 합치기: [4, 8], [3, 7]로 작은 단위끼리 정렬 후 합친다. 이어서 [3, 4, 7, 8], [1, 2, 5, 6]로 합치고, 최종적으로 [1, 2, 3, 4, 5, 6, 7, 8]로 정렬된다.

합병 정렬의 장점 🌟

• 안정적인 정렬: 데이터의 순서를 유지하는 안정적인 정렬 방법이다.
• 효율성: 리스트의 크기가 커질수록 빠른 정렬이 가능하다. 일반적으로 (O(n \log n))의 시간 복잡도를 가진다.

코드 예시 👩‍💻

#include <stdio.h>
int sorted[100],count;

void merge(int list[], int left,int mid, int right) {
    int i,j,k,l;
    i=left;
    j=mid+1;
    k=left;
    
    while(i<=mid && j<=right) {
        if(list[i]<=list[j]) sorted[k++]=list[i++];
        else sorted[k++]=list[j++];
    }
    
    if(i>mid) for(l=j; l<=right; l++) sorted[k++]=list[l];
    else for(l=i; l<=mid; l++) sorted[k++]=list[l];
    for(l=left; l<=right; l++) list[l]=sorted[l];
}

void mergesort(int list[], int left,int right) {
    int mid;
    if(left<right) {
        mid=(left+right)/2;
        mergesort(list,left,mid);
        mergesort(list,mid+1,right);
        merge(list,left,mid,right);
    }
}

int main() {
    int list[4]={27,12,20,25};
    mergesort(list,0,3);
    for(int i=0; i<4; i++) printf("%d ",list[i]);
    return 0;
}

정리 📝

합병 정렬은 데이터를 작은 단위로 나누고, 정렬 후 다시 합쳐서 전체를 정렬하는 방식이다.