[JAVA] 병합 정렬 개념 및 알고리즘을 이용한 코딩#1

병합 정렬 개념

병합 정렬은 여러 개의 정렬된 자료의 집합을 결합해 하나의 집합으로 만드는 정렬 방법이다. 이 정렬은 전체를 상대로 수행하지 않고 분할(Divide)한 뒤 각 부분집합들에 대해 정렬한 후 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다.

매일프로그래밍 문제 기준

1. 문제
   두 개의 정렬된 배열 X, Y가 주어졌을 때, 두 배열의 크기를 유지하면서 두 배열의 전체를 정렬하시오.
   즉, 배열 X에는 작은 수들로 배열 Y에는 큰 수들로 구성되고 원소들은 정렬되어 있어야 합니다. 단, 정렬 시 다른 자료 구조를 사용하지 않고 주어진 배열만을 이용해야 합니다.

문제의 핵심은 주어진 배열만을 이용하는것 입니다. 주어진 배열로 Output을 처리하려면 병합정렬을 사용하면 됩니다.

Input
X: [1, 4, 7, 8, 10]
Y: [2, 3, 9]

Output
X: [1, 2, 3, 4, 7]
Y: [8, 9, 10]

2. 풀이
   X 배열의 원소를 돌면서 각 원소가 Y 배열의 첫번째 원소보다 크면 두 원소를 교환 합니다. 교환 후 Y 배열을 정렬 상태로 유지하기 위해 Y 배열을 순회 하면서 Y[0]의 원소를 정렬된 위치로 이동합니다. 이 과정이 병합 정렬 방법과 비슷합니다.
   다른 점은 병합을 위해 보조 배열을 사용하지 않는다는 점입니다.

class Merge
{
    // 두 개의 정렬된 배열 X, Y를 배열 내에서 병합, 배열 X, Y의 크기는 변하지 않고 전체 원소가 정렬됨
    public static void merge(int[] X, int[] Y)
    {
        int m = X.length;
        int n = Y.length;

        // 배열 X의 각 원소 X[i]를 순회
        // X[i]가 이미 정렬된 위치라면 무시
        // 그렇지 않다면 Y의 첫번째에 위치한 작은 원소와 교환
        for (int i = 0; i < m; i++)
        {
            // X 배열의 현재 원소를 Y 배열의 첫번째 원소와 비교
            if (X[i] > Y[0])
            {
                // X[i]와 Y[0]를 교환
                int temp = X[i];
                X[i] = Y[0];
                Y[0] = temp;

                int first = Y[0];

                // Y 배열의 정렬을 유지하기 위해 Y[0]를 정렬된 위치로 이동
                int k;
                for (k = 1; k < n && Y[k] < first; k++) {
                    Y[k - 1] = Y[k]; //first값이 더 크기 때문에 한칸씩 앞으로 이동시킵니다.
                }
                Y[k - 1] = first; //이동이 완료되었다면 k값 위치가 정해져 있기때문에 마지막으로 first값을 넣어줍니다.
            }
        }
    }

    // 메인 함수
    public static void main (String[] args)
    {
        int[] X = { 1, 4, 7, 8, 10 };
        int[] Y = { 2, 3, 9 };

        merge(X, Y);

        System.out.println("X: " + Arrays.toString(X));
        System.out.println("Y: " + Arrays.toString(Y));
    }
}

결과