병합정렬

기존의 데이터 집합단위를 더이상 나눌수 없는 크기가 될때까지 분할한 뒤

임시 저장공간에 순서를 저장하며 재조합하며 정렬하는 방식

 

평균 시간복잡도는 분할단계로 집합을 절반씩 분할하므로 O(logN) 의 시간복잡도를 갖고

병합단계 모든요소가 비교되므로 O(N) 의 시간복잡도를 갖게 되므로

전체적인 시간복잡도는 O(N log N) 로 안정적인 성능을 제공하지만

주어진 집합요소(배열 , 리스트)가 있을때 임시로 저장해둘 똑같은 크기의 집합요소가 더 필요하게 된다.

 

또한 해당 알고리즘 구현시 데이터들을 다시 함수에 넣어줘야하므로 재귀에 대한 개념도 필요하며

두개의 집합으로만 정렬된 데이터를 구현하기위해 여러개의 포인터를 다뤄야하므로 구현이 조금 복잡할수 있다.

 

처음 알고리즘을 접하게될때 그림을 보고 조금 혼란스러웠던점은

그림처럼 정말 데이터를 나누는게 아니고, 재귀 함수를 이용해 탐색 지점(Index)을 잡아두는것이다.

그림은 단지 해당 알고리즘의 원리만 이해할수있게 표현되었다는점을 참고한다.

 

위쪽 34 , 12가 병합될때도 그림 아래쪽과 같이 tempArr를 사용한다는점이 생략되었다.

전체적인 코드 흐름은 이러하다.

 

문제

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

풀이

using System.Text;

StringBuilder sb = new StringBuilder();

int count = int.Parse(Console.ReadLine());

int[] arr = new int[count];
int[] tempArr = new int[count];

for (int i = 0; i < count; i++)
{
    arr[i] = int.Parse(Console.ReadLine());
}

Partition(0,arr.Length-1);

for (int i = 0; i < arr.Length; i++)
{
    sb.AppendLine($"{arr[i]}");
}

System.Console.Write(sb);

void Merge(int left, int right)
{
    int mid = (left + right) / 2;
    int idx1 = left;
    int idx2 = mid + 1;
    int tempArrPointer = left;

    while (true)
    {
        if( idx1 > mid || idx2 > right)
            break;

        if(arr[idx1] > arr[idx2])
            tempArr[tempArrPointer++] = arr[idx2++];

        else
            tempArr[tempArrPointer++] = arr[idx1++];
    }

    if(idx1 > mid)
    {
        while (true)
        {
            if(idx2 > right)
                break;

            tempArr[tempArrPointer++] = arr[idx2++];
        }
    }

    else
    {
        while (true)
        {
            if(idx1 > mid)
                break;

            tempArr[tempArrPointer++] = arr[idx1++];
        }
    }

    for (int i = left; i <= right; i++)
    {
        arr[i] = tempArr[i];
    }
}

void Partition(int left, int right)
{
    int mid;

    if(left < right)
    {
        mid = (left + right) /2;
        Partition(left,mid);
        Partition(mid+1,right);
        Merge(left,right);
    }
}