[Java] 고급 정렬 - 병합 정렬이란? (개념/ 예제/ 총 정리)

서론

---

이번 글에서는 고급 정렬 알고리즘에 속한 병합 정렬을 예제를 통해 알아보도록 하겠습니다. 

 

---

 

병합 정렬(Merge Sort)이란?

---

병합 정렬은 재귀 용법을 활용한 정렬 알고리즘을 말한다. 구현 방식은 다음과 같다.

 

 

병합 정렬의 방식

구현 방식 (위 이미지 참고)

1. 리스트를 절반으로 잘라 비슷한 크기의 두 개의 리스트로 나눈다.
2. 각 리스트를 재귀적으로 합병 정렬을 이용하여 정렬한다.
3. 두 리스트를 다시 하나의 정렬된 리스트로 병합한다.

위와 같이 방식을 3 Step으로 나누어 구현할 수 있다. 이 방식을 토대로 아래의 예제 문제를 풀어보자.

---

 

예제

---

구현 방식에서 1번 항목인 하나의 리스트를 두 개의 리스트로 나누는 것부터 구현을 해보면 다음과 같이 짜볼 수 있다.

 

두 개의 리스트로 나눠보기

public class Split {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0; i<10; i++)
            list.add(i,(int)(Math.random() * 100));

        split(list);
    }

    private static void split(ArrayList<Integer> list){
        if(list.size() <=1)
            return;

        int mediumSize = list.size() / 2;

        List<Integer> leftArray = list.subList(0, mediumSize);
        List<Integer> rightArray = list.subList(mediumSize, list.size());

        System.out.println(leftArray);
        System.out.println(rightArray);
    }
}

출력 값

위의 소스를 간략히 설명하면, list에 10개의 random값을 넣은 후 List에서 제공해주는 sublist 함수를 통해 배열을 left, right로 쪼개어 출력하였다.  이제 위의 로직을 참고하여 병합 정렬을 구현해보자.

 

병합 정렬 구현

public class MergeSort {

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<20; i++)
            list.add((int)(Math.random() * 100));

        System.out.println(mergeSplit(list));
    }

    private static List<Integer> mergeSplit(List<Integer> list){
        if (list.size() <= 1)
            return list;
        
        int mediumSize = list.size() / 2;

        List<Integer> leftArray = mergeSplit(list.subList(0, mediumSize));
        List<Integer> rightArray = mergeSplit(list.subList(mediumSize, list.size()));

        return mergeFunc(leftArray, rightArray);
    }

    private static ArrayList<Integer> mergeFunc(List<Integer> leftArray, List<Integer> rightArray) {
        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        int leftIdx = 0;
        int rightIdx = 0;

        // Order 1 : left/right 둘다 있을 때
        while(leftArray.size() > leftIdx && rightArray.size() > rightIdx){

            // 좌측이 클 경우 우측 값을 mergedList에 넣는다.
            if (leftArray.get(leftIdx) > rightArray.get(rightIdx)) {
                mergedList.add(rightArray.get(rightIdx));
                rightIdx += 1;
            } else {
                mergedList.add(leftArray.get(leftIdx));
                leftIdx += 1;
            }
        }

        // Order 2 : right 데이터가 없을 때 -> left 데이터가 남아 있다면
        while(leftArray.size() > leftIdx){
            //left 데이터를 mergedList에 채워 넣기
            mergedList.add(leftArray.get(leftIdx));
            leftIdx += 1;
        }

        // Order 3 : left 데이터가 없을 때
        while(rightArray.size() > rightIdx){
            mergedList.add(rightArray.get(rightIdx));
            rightIdx += 1;
        }

        return mergedList;
    }
}

출력 값

위의 병합 정렬을 구현한 로직을 살펴보면 쉽게 이해가 안갈 수 있지만 처음 말했던 구현 방식 부분을 읽어보고 다시 한번 읽어보면 그리 어렵지않다.

 

일단 위의 로직도 설명해보자면, 리스트를 두 개의 left, right 리스트로 쪼갠 후 mergeFunc를 타게 만들어 정렬을 하게끔 만들었다.

 

그 후 Order 1, 2, 3을 타게 되는데 하나 씩 알아보면 다음과 같다.

 

mergeFunc 구조

• Order 1
  • leftArray , rightArray의 값이 둘 다 있을 때
    • 만약 leftIdx, righIdx가 이미 leftArray 또는 rightArray 배열을 다 순회했다면 그 반대쪽 데이터를 그대로 넣고 해당 인덱스를 1 증가 시키는 로직
• Order2
  • rightArray의 값만 없을 때
    • 나머지 leftArray에 있는 데이터를 그대로 mergedList에 넣는 로직
• Order 3
  • leftArray의 값만 없을 때
    • 나머지 rightArray에 있는 데이터를 그대로 mergedList에 넣는 로직

 

위와 같이 병합 정렬을 구현하였을 때 시간 복잡도는 O(n log n)이 된다. (참고)