알고리즘 노팅 - 정렬 종류와 구현(병합정렬)

1. ToDo

- 그냥 문득 내용을 공부하면서 정리하고 싶어진 정렬 알고리즘

---

2. 종류

• 선택 정렬

• 삽입 정렬

• 버블 정렬

• 합병 정렬

• 퀵 정렬

---

3. 개념설명

• 글로 끄적..
  
  병합 정렬은 3단계로 나누어 정렬하는 방식이다. 우선 시간 복잡도는 O(nlogn)이므로 지금까지 설명한 선택, 삽입, 버블에 비해 가장 오래 걸리는 시간 복잡도를 가지고 있다. 정렬 단계로는 분할(Devide), 정복(Conquer), 결합(Combine)이 있다.

  • 1단계) 분할 : 배열을 같은 크기의 원소 2개씩의 배열로 분할한다.
  • 2단계) 정복 : 나눠진 배열을 정렬한다. 부분 배열의 크기가 충분하지 않을 시 분할과 정복 과정을 반복한다.
  • 3단계) 결합 : 정렬된 부분 배열들을 하나의 배열로 합친다.

• 👍  위의 3단계를 반복하여 정렬을 하는데 이 과정은 추가적인 배열 또는 리스트 등이 필요하다.
  

• 그림으로 쓱삭..
  
  단계별로 나눠져 있어서 글로는 설명했지만 그림이 더 쉬울 듯하여 참고될만한 페이지 링크를 포함하겠다.
  (참고 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html)
  
  
  
  

---

4. 코드로 투닥투닥.. (C#)

static void Main(string[] args)
{
    int[] array = { 7, 5, 4, 3, 8, 9, 10, 2, 6, 1 };
    MergeListSort(array, 0, array.Count() - 1);
}

private static void Merge(int[] array, int start, int mid, int end)
{
    int[] result = new int[end + 1];
    int low = start, high = mid + 1, key = start;

    while (low <= mid && high <= end)
    {
        if(array[low] < array[high])
        {
            result[key] = array[low];
            low++;
        }
        else
        {
            result[key] = array[high];
            high++;
        }
        key++;
    }

    if (low > mid)
    {
        for(; high <= end; high++)
        {
            result[key] = array[high];
            key++;
        }
    }
    else
    {
        for(; low <= mid; low++)
        {
            result[key] = array[low];
            key++;
        }
    }

    for(int i = start; i <= end; i++)
    {
        array[i] = result[i];
    }

    for (int i = 0; i < array.Count(); i++)
    {
        Console.Write(array[i]);
    }
    Console.WriteLine();
}

private static void MergeListSort(int[] target, int start, int end)
{
    if (start < end)
    {
        int mid = ((start + end) / 2);

        MergeListSort(target, start, mid);
        MergeListSort(target, mid + 1, end);
        Merge(target, start, mid, end);
    }
}