합병정렬 알고리즘 with 상화쌤

🧐 합병정렬이란?

분할 정복 알고리즘!

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,
두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것

☑️ 장단점

장점

• 빠른속도를 자랑합니다.
  데이터의 영향을 작게받아서 최악, 평균, 최선의 경우 모두 O(n log n)의 시간 복잡도를 가집니다.

• 큰 데이터 정렬에 적합합니다.
  메모리에 다 담을 수 없는 큰 파일을 정렬해야 할 때, 하드 디스크 등의 외부 저장 장치를 활용해 부분적으로 나눠서 정렬한 후 병합하는 방식으로 사용할 수 있습니다

단점

• 작은 데이터에서는 오히려 비효율적
  작은 데이터에서는 오히려 비효율적이어서 삽입 정렬 같은 알고리즘보다 느릴 수 있습니다.

• 병합 과정에서 추가적인 연산 필요
  병합 과정에서 추가적인 연산 필요하여 배열을 쪼개고 병합하는 과정이 많아 캐시 효율성이 떨어질 수 있습니다.

🛠️ 방법

1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

2. 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.

3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합한다.

코드

#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;
}

마무리

퀵정렬, 합병정렬등 상황에 맞게 써야겠다