병합 merge 알고리즘

병합 알고리즘

        public static void Main(string[] args)
        {
            // 오름차순 정렬된 두 배열
            int[] first = { 1, 3, 5 };
            int[] second = { 2, 4 };
            // 각 배열의 길이
            int M = first.Length;
            int N = second.Length;
            // 합칠 배열의 길이를 합칠 배열의 길이의 합으로 정함
            int[] merge = new int[M + N];
            // 순서대로 first,second,merge의 인덱스 값
            int i = 0; int j = 0; int k = 0;

            // 둘 중 하나라도 배열의 끝에 도달할 때 까지
            while(i < M && j < N)
            {
                // 더 작은 값을 merge 배열에 저장
                if(first[i] <= second[j])
                {
                    merge[k++] = first[i++];
                }
                else
                {
                    merge[k++] = second[j++];
                }
            }
            // 첫 번째 배열이 끝에 도달할 때 까지
            while(i < M)
            {
                merge[k++] = first[i++];
            }
            // 두 번째 배열이 끝에 도달할 때 까지
            while(j < N)
            {
                merge[k++] = second[j++];
            }
        }

1. while 문으로 오름차순으로 정렬되어 있는 두 배열 중 하나라도 배열의 끝에 다다를 때 까지 반복을 실행한다.
2. 두 배열을 비교해서 더 작은 수를 가지고 있으면 merge 배열에 집어넣고 자신의 인덱스 카운트와 merge의 인덱스 카운트를 증가시킨다.
3. 만약 반복문이 끝났다면 그것은 두 배열 중 하나 이상이 배열의 끝에 다다랐다는 뜻이다.
4. 두 배열의 크기가 다를 수 있기 때문에 추가로 while 반복문을 만들어 각자의 배열의 길이만큼 돌려서 남아있는 값을 merge에 넣게 한다. 물론 이때도 자신의 인덱스 카운트와 merge의 인덱스 카운트를 증가시킨다.

 

확장 메소드

        public static void Main(string[] args)
        {
            // 오름차순 정렬된 두 배열
            int[] first = { 1, 3, 5 };
            int[] second = { 2, 4 };

            int[] merge = first.Union(second).OrderBy(m => m).ToArray();
        }

 

참조: https://www.youtube.com/watch?v=jXArdum1Qzg&list=PLO56HZSjrPTD8FIsr5tIO_foTN_kmXLEM&index=12