병합 정렬 C# 콘솔로 구현 (merge sort)

개요

 

앞선 글들에서 병합정렬의 원리에 대해서 배웠습니다. 이를 바탕으로 C# 콘솔 앱으로 실습을 해보겠습니다.

 

 

 

---

 

 

 

풀이1 - 병합정렬 함수 구현

 

public static void MergeSort(int[] array, int beginIndex, int endIndex)
{
    if (beginIndex < endIndex)
    {
        int midIndex = (beginIndex + endIndex) / 2;
        MergeSort(array, beginIndex, midIndex);
        MergeSort(array, midIndex + 1, array.Length - 1);
        Merge(array, 0, midIndex, array.Length - 1);
    }
}

병합정렬을 구현했습니다. 나름대로 복습을 하기 위해서 인자명은 제 나름대로 바꿔봤습니다. 코드를 따라하는 경우에는 이렇게 변수명을 내 입맛에 바꾸는게 조금 더 기억에 오래 남는것같네요.

 

원래는 분할 단계에서 배열의 중간 인덱스 값을 구할 때 내림을 해줘야하지만 그냥 안해줬습니다. 어차피... 인트로 받아오면 소수점 이하는 짤려나가기 때문입니다.

 

 

 

---

 

 

 

풀이2 - 병합 함수 구현

 

public static void Merge(int[] array, int beginIndex, int midIndex, int endIndex)
{
    int[] lowHalf = new int[midIndex + 1];
    int[] highHalf = new int[endIndex - midIndex];

    int k = beginIndex;
    int i = 0;
    int j = 0;

    for (i = 0; k <= midIndex; i++, k++)
    {
        lowHalf[i] = array[k];
    }
    for (j = 0; k <= endIndex; j++, k++)
    {
        highHalf[j] = array[k];
    }

    k = beginIndex;
    i = 0;
    j = 0;

    while (i < lowHalf.Length && j < highHalf.Length)
    {
        if (lowHalf[i] < highHalf[j])
        {
            array[k] = lowHalf[i];
            i++;
        }
        else
        {
            array[k] = highHalf[j];
            j++;
        }

        k++;
    }
    while (i < lowHalf.Length)
    {
        array[k] = lowHalf[i];
        i++; k++;
    }
    while (j < highHalf.Length)
    {
        array[k] = highHalf[j];
        j++; k++;
    }
}

과정의 설명은 지난 글을 확인해주세요.

 

 

 

---

 

 

 

결과 - 콘솔앱으로 입력받고 출력해보기

 

정상 출력 됩니다.

 

 

---

 

 

 

분석 - 병합 정렬 분석하기

 

-작성예정-