C# 코딩테스트 강좌, 병합 정렬

코딩 테스트가 갈수록 인기를 끌고 있는 현 시점에서, 알고리즘 문제는 필수적으로 알아둬야 할 주제입니다. 이 글에서는 병합 정렬(Merge Sort) 알고리즘에 대해 심층적으로 다루어 보겠습니다. 병합 정렬은 일반적으로 좋은 성능을 발휘하는 정렬 알고리즘 중 하나로, ‘분할 정복(Divide and Conquer)’ 전략을 기반으로 합니다. 이 글에서는 병합 정렬의 원리, 구현 방법, 그리고 실제 문제를 통해 병합 정렬을 활용하는 방법을 설명하겠습니다.

1. 병합 정렬 개요

병합 정렬은 리스트를 분할하고 정렬한 다음에 병합하는 방식으로 작동합니다. 데이터 구조의 장점과 시간 복잡도를 고려해야 하는 여러 상황에서 유용하게 쓰일 수 있습니다. 병합 정렬은 평균, 최악, 그리고 최선의 경우 모두 O(n log n)의 시간 복잡도를 가지며, 안정적인 정렬 알고리즘입니다. 즉, 동일한 값을 가진 데이터의 상대적인 순서를 유지합니다.

1.1. 병합 정렬 작동 원리

병합 정렬은 다음과 같은 과정을 통해 진행됩니다:

리스트를 반으로 나누고, 각 부분 리스트를 재귀적으로 정렬합니다.
정렬된 부분 리스트를 병합하여 하나의 정렬된 리스트를 만듭니다.

이 과정을 통해 리스트의 길이가 1이 될 때까지 나누고, 이 후 조합으로 다시 정렬하게 됩니다. 아래의 그림은 병합 정렬의 기본적인 흐름을 보여줍니다:

2. 병합 정렬 구현

병합 정렬을 C#로 구현해 보겠습니다. 기본적인 구현은 다음과 같습니다:

using System;

class MergeSort
{
    // 메인 메서드
    static void Main(string[] args)
    {
        int[] array = {38, 27, 43, 3, 9, 82, 10};

        Console.WriteLine("정렬 전: " + string.Join(", ", array));
        MergeSortAlgorithm(array, 0, array.Length - 1);
        Console.WriteLine("정렬 후: " + string.Join(", ", array));
    }

    // 병합 정렬 알고리즘
    static void MergeSortAlgorithm(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            // 분할
            MergeSortAlgorithm(array, left, mid);
            MergeSortAlgorithm(array, mid + 1, right);

            // 병합
            Merge(array, left, mid, right);
        }
    }

    // 병합 메서드
    static void Merge(int[] array, int left, int mid, int right)
    {
        // 두 개의 서브 배열 만들기
        int[] leftArray = new int[mid - left + 1];
        int[] rightArray = new int[right - mid];

        for (int i = 0; i < leftArray.Length; i++)
            leftArray[i] = array[left + i];

        for (int j = 0; j < rightArray.Length; j++)
            rightArray[j] = array[mid + 1 + j];

        int k = left;
        int a = 0;
        int b = 0;

        // 배열 병합
        while (a < leftArray.Length && b < rightArray.Length)
        {
            if (leftArray[a] <= rightArray[b])
            {
                array[k] = leftArray[a];
                a++;
            }
            else
            {
                array[k] = rightArray[b];
                b++;
            }
            k++;
        }

        // 남은 요소들 병합
        while (a < leftArray.Length)
        {
            array[k] = leftArray[a];
            a++;
            k++;
        }

        while (b < rightArray.Length)
        {
            array[k] = rightArray[b];
            b++;
            k++;
        }
    }
}

2.1. 코드 설명

MergeSortAlgorithm: 이 메서드는 배열을 반으로 나누고 재귀 호출을 통해 정렬합니다. 좌측과 우측의 서브 배열을 정렬한 후 Merge 메서드를 호출하여 병합합니다.
Merge: 이 메서드는 두 개의 서브 배열을 받아 그 배열들을 병합하여 최종 정렬된 배열로 만듭니다. 각각의 포인터를 사용하여 두 서브 배열의 요소를 비교하고, 더 작은 값을 최종 배열에 추가합니다.

3. 문제 예제

이제 병합 정렬 알고리즘을 적용해 볼 수 있는 간단한 문제를 생각해 보겠습니다.

문제: 정수 리스트 정렬하기

주어진 정수 리스트를 오름차순으로 정렬하는 메서드를 작성하시오. 입력은 1에서 1,000,000 사이의 정수 값으로 구성된 배열이며, 최대 1,000개의 요소를 가질 수 있다. 병합 정렬을 사용하여 문제를 해결하세요.

입력 예시

{8, 3, 1, 7, 0, 10, 2}

출력 예시

{0, 1, 2, 3, 7, 8, 10}

3.1. 문제 해결 과정

위 문제를 병합 정렬 알고리즘을 통해 해결하기 위해서는 앞서 작성한 병합 정렬 알고리즘을 그대로 사용할 수 있습니다. 코드를 여기에 채워 넣고, 입력값을 여러 개 테스트해 보는 것도 도움이 될 것입니다.

using System;

class SortingExample
{
    static void Main(string[] args)
    {
        int[] array = {8, 3, 1, 7, 0, 10, 2};
        MergeSort(array);
        Console.WriteLine("정렬된 배열: " + string.Join(", ", array));
    }

    // 병합 정렬 호출 메서드
    static void MergeSort(int[] array)
    {
        MergeSortAlgorithm(array, 0, array.Length - 1);
    }

    // [이곳에 위의 MergeSortAlgorithm과 Merge 메서드를 추가하세요]
}

이렇게 작성된 메서드를 통해, 주어진 정수 리스트를 오름차순으로 정렬할 수 있습니다. 여러 입력값을 통해 다양한 테스트를 거쳐, 알고리즘의 유효성을 확인하는 것이 좋습니다.

4. 병합 정렬의 장점과 단점

4.1. 장점

안정적인 정렬: 같은 값의 데이터들이 원래 순서를 유지하면서 정렬됩니다.
예측 가능한 성능: 최악의 경우에도 O(n log n)의 복잡도를 보장합니다.
대량의 데이터 처리: 큰 데이터셋에서도 성능이 일관되며, 외부 정렬에 대한 구현이 용이합니다.

4.2. 단점

추가 공간 요구: 정렬을 위해 추가적인 메모리가 필요합니다.
소규모 데이터에서는 비효율적: 소규모 데이터에서는 단순한 정렬 방법이 더 빠를 수 있습니다.

5. 마치며

이번 포스트에서는 병합 정렬 알고리즘에 대해 상세히 알아봤습니다. 구체적인 구현을 통해 실제 문제 해결 과정에서도 어떻게 활용할 수 있는지를 살펴보았습니다. 효율적이고 안정적인 정렬을 위해 병합 정렬이 적합하게 작용할 수 있으며, 다양한 알고리즘 문제를 푸는 데 있어서 매우 유용한 도구가 될 것입니다. 다음 포스트에서도 다양한 알고리즘을 다뤄보겠습니다. 감사합니다!