[알고리즘] 병합 정렬

1. 병합 정렬 (분할 정복 전략을 사용)

  - 재귀 용법을 활용한 정렬 알고리즘이다.

  - 리스트를 절반으로 잘라서 비슷한 크기의 두 부분 리스트로 나눈다.

  - 각 부분 리스트를 재귀적으로 합병 정렬을 이용하여 정렬시킨다.

  - 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

 

 

 

2. 알고리즘의 이해 

 

  - 두 단계로 분리해서 이해한다.

    - 1단계 : 정렬되지 않은 배열을 끝까지 분리하는 단계 

    - 2단계 : 분리한 데이터를 단계별로 합치는 단계

 

 

2-1. 예제 

- data = [1, 9, 3, 2] 일 때 

 

- 먼저 [1, 9], [3, 2]로 나눈다.

- 다시 앞부분을 [1], [9] 로 나누고 (1단계)

- 다시 정렬해서 합친다. [1, 9] (2단계)

- [3, 2]는 [3], [2] 로 나누고

- 다시 정렬하여 합친다. [2, 3]

- 이제 [1, 9], [2, 3] 을 합친다.

- 두 배열의 맨 앞에 위치한 데이터 부터 각각 비교하며 정렬된 합쳐진 배열을 작성한다. 각각의 원소를 포인터로 비교한다.

 

 

 

 

3. 알고리즘 구현 

 

- 배열을 앞, 뒤  두 배열로 짜르는 코드 작성하기 

public class Split {

    public void splitFunc(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return;
        }
        int medium = dataList.size() / 2;

        ArrayList<Integer> leftArr = new ArrayList<>(dataList.subList(0, medium)); // 0부터 medium-1 인덱스 번호까지
        ArrayList<Integer> rightArr = new ArrayList<>(dataList.subList(medium, dataList.size())); // 0부터 medium-1 인덱스 번호까지
    }
}

- 배열의 개수가 1개일 경우 해당 값을 리턴한다.

- 그렇지 않다면 배열을 앞, 뒤 2개로 나눈다.

 

 

 

 

- 병합 정렬을 위한 메서드 만들기 (전체)

 

import java.util.*;

public class Split {

    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int medium = dataList.size() / 2;

        ArrayList<Integer> leftArr = this.mergeSplitFunc(new ArrayList<>(dataList.subList(0, medium))); // 0부터 medium-1 인덱스 번호까지
        ArrayList<Integer> rightArr = this.mergeSplitFunc(new ArrayList<>(dataList.subList(medium, dataList.size()))); // 0부터 medium-1 인덱스 번호까지

        return this.mergeFunc(leftArr, rightArr);

    }

    private ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
        ArrayList<Integer> mergeList = new ArrayList<>();
        int leftPoint = 0;
        int rightPoint = 0;

        //CASE 1 : left, right 둘 다 있을 때
        while (leftList.size() > leftPoint && rightList.size() > rightPoint) {
            if (leftList.get(leftPoint) > rightList.get(rightPoint)) {
                mergeList.add(rightList.get(rightPoint));
                rightPoint++;
            } else {
                mergeList.add(leftList.get(leftPoint));
                leftPoint++;
            }
        }

        //CASE 2 : right 데이터가 없을 때
        while (leftList.size() > leftPoint) {
            mergeList.add(leftList.get(leftPoint));
            leftPoint++;
        }

        //CASE 3 : left 데이터가 없을 때
        while (rightList.size() > rightPoint) {
            mergeList.add(rightList.get(rightPoint));
            rightPoint++;
        }

        return mergeList;
    }

}

- mergeFunc 가 leftArr, rightArr을 합쳐서 정렬한 배열을 리턴한다고 가정하면 left, right는 이미 정렬된 배열이다.