[Algorithm] 15장 고급 정렬 - 병합 정렬

1 분 소요

병합 정렬(merge sort)

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

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

구현

재귀용법 틀를 먼저만들어본다.

배열의 갯수가 한개이면 해당 값 리턴
한개가 아니면 배열을 두개로 나눈다.

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

        int medium = dataList.size()/2;
        ArrayList<Integer> leftArr;
        ArrayList<Integer> rightArr;

        leftArr = mergeSplitFunc(new ArrayList<>(dataList.subList(0,medium)));
        rightArr = mergeSplitFunc(new ArrayList<>(dataList.subList(medium,dataList.size())));

        return mergeFunc(leftArr,rightArr);
    }

mergeFunc 함수는 아직 만들기 전이다. mergeFunc 함수가 leftArr과 rightArr를 합쳐서 정렬한 배열을 리턴한다.

합병과 재정렬하는 함수를 만든다.

public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftArr, ArrayList<Integer> rightArr){
        ArrayList<Integer> mergeList = new ArrayList<>();

        int leftPoint = 0;
        int rightPoint = 0;

        while (leftArr.size()>leftPoint && rightArr.size()>rightPoint){
            if (leftArr.get(leftPoint)>rightArr.get(rightPoint)){
                mergeList.add(rightArr.get(rightPoint));
                rightPoint++;
            }else {
                mergeList.add(leftArr.get(leftPoint));
                leftPoint++;
            }
        }

        while (leftArr.size()>leftPoint){
            mergeList.add(leftArr.get(leftPoint));
            leftPoint++;
        }

        while (rightArr.size()>rightPoint){
            mergeList.add(rightArr.get(rightPoint));
            rightPoint++;
        }

        return mergeList;
    }

최종 코드는 다음과 같다.

public class MergeSort {
    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList){
        if (dataList.size()<=1){
            return dataList;
        }

        int medium = dataList.size()/2;
        ArrayList<Integer> leftArr;
        ArrayList<Integer> rightArr;

        leftArr = mergeSplitFunc(new ArrayList<>(dataList.subList(0,medium)));
        rightArr = mergeSplitFunc(new ArrayList<>(dataList.subList(medium,dataList.size())));

        return mergeFunc(leftArr,rightArr);
    }

    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftArr, ArrayList<Integer> rightArr){
        ArrayList<Integer> mergeList = new ArrayList<>();

        int leftPoint = 0;
        int rightPoint = 0;

        while (leftArr.size()>leftPoint && rightArr.size()>rightPoint){
            if (leftArr.get(leftPoint)>rightArr.get(rightPoint)){
                mergeList.add(rightArr.get(rightPoint));
                rightPoint++;
            }else {
                mergeList.add(leftArr.get(leftPoint));
                leftPoint++;
            }
        }

        while (leftArr.size()>leftPoint){
            mergeList.add(leftArr.get(leftPoint));
            leftPoint++;
        }

        while (rightArr.size()>rightPoint){
            mergeList.add(rightArr.get(rightPoint));
            rightPoint++;
        }

        return mergeList;
    }

    public static void main(String[] args) {
        ArrayList<Integer> testData = new ArrayList<>();

        for (int index = 0; index < 100; index++) {
            testData.add((int)(Math.random() * 100));
        }
        MergeSort mSort = new MergeSort();
        System.out.println(mSort.mergeSplitFunc(testData));
    }
}