병합

 

 

 

분할정복 기법을 정렬에서 적용한 정렬 방법이다.

 

1. 정렬되지 않은 배열을 하나의 원소로 분리

2. 분리된 원소를 정렬하며 병합

 

두 단계로 구성된다.

 

 

<분리 단계>

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

    ArrayList<Integer> leftArr = new ArrayList<Integer>();
    ArrayList<Integer> rightArr = new ArrayList<Integer>();

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

    return mergeFunc(leftArr, rightArr); // merge함수는 뒤에서 구현.
    
    // 재귀 용법을 사용해 리스트를 분할한다.
}

 

 

 

<합병 단계>

public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
    ArrayList<Integer> mergedList = new ArrayList<Integer>();
    int leftPoint = 0;
    int rightPoint = 0;
    
    // 리스트를 합칠 때 left와 right가 모두 있다는 보장이 없다. 경우를 나눠서 접근하자.
    // 총  세 가지 경우로 나뉘고, 세가지 while문을 모두 거쳐 mergesort에 정렬된 요소를 저장한다.
    // 정렬할 때 각각의 원소들은 이미 정렬된 상태임을 인지하자.
    
     // CASE1: left/right 둘 다 있을 때
    while (leftList.size() > leftPoint && rightList.size() > rightPoint) {
        if (leftList.get(leftPoint) > rightList.get(rightPoint)) {
            mergedList.add(rightList.get(rightPoint));
            rightPoint += 1;
        } else {
            mergedList.add(leftList.get(leftPoint));
            leftPoint += 1;
        }
    }
    
    // leftpoint나 rightpoint가 범위를 벗어나게 되면 while문이 끝난다.
    // 아직 정렬되지 못한 부분은 아래 두 개의 while문을 통해 마무리된다,

    // CASE2: right 데이터가 없을 때
    while (leftList.size() > leftPoint) {
        mergedList.add(leftList.get(leftPoint));
        leftPoint += 1;
    }
    
    // CASE3: left 데이터가 없을 때
    while (rightList.size() > rightPoint) {
        mergedList.add(rightList.get(rightPoint));
        rightPoint += 1;
    }
    
    return mergedList;
}

 

 

 

<최종>

 

import java.util.*;


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

        for (int index = 0; index < 100; index++) {
            testData.add((int) (Math.random() * 100));
        }
        ArrayList<Integer> asdf = new ArrayList<>();
        asdf.add(7);
        asdf.add(7);
        asdf.add(6);
        

        MergeSort mSort = new MergeSort();
        System.out.println(mSort.mergeSplitFunc(asdf));

    }
}

class MergeSort {
    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        int leftPoint = 0;
        int rightPoint = 0;

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

        // CASE2: right 데이터가 없을 때
        while (leftList.size() > leftPoint) {
            mergedList.add(leftList.get(leftPoint));
            leftPoint += 1;
        }

        // CASE3: left 데이터가 없을 때
        while (rightList.size() > rightPoint) {
            mergedList.add(rightList.get(rightPoint));
            rightPoint += 1;
        }

        return mergedList;
    }

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

        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();

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

        return this.mergeFunc(leftArr, rightArr);
    }

}

 

 

 

시간복잡도 : O(n logn)