☕️ [JAVA] 병합 정렬

자바로 병합정렬 알고리즘을 구현해 보았습니다. 

 

병합정렬이란 

 

배열을 받아서 배열을 나눌 수 있을  때 까지 반으로 쪼개고 

 

쪼갤 수 없을 때 하나씩 대 소를 비교해서 병합하는 정렬 알고리즘입니다. 

 

정렬 시간복잡도는 (nlogn)입니다. 

 

병합 정렬에서는 재귀용법이 사용되어서 머리가 빠개질수도 있지만 찬찬히 살펴보면 크게 어렵지 않습니다. 

 

https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

import java.util.ArrayList;

public class MergeSort {
	
    // 배열을 합치는 함수 
    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftData, ArrayList<Integer> rightData) {
        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        int leftIdx = 0;
        int rightIdx = 0;

        while (leftData.size()>leftIdx && rightData.size()>rightIdx){
            if (leftData.get(leftIdx) > rightData.get(rightIdx)) {
                mergedList.add(rightData.get(rightIdx));
                rightIdx+=1;
            } else {
                mergedList.add(leftData.get(leftIdx));
                leftIdx+=1;
            }
        }
        while (leftData.size() > leftIdx) {
            mergedList.add(leftData.get(leftIdx));
            leftIdx +=1;
        }
        while (rightData.size() > rightIdx) {
            mergedList.add(rightData.get(rightIdx));
            rightIdx +=1;
        }
        return mergedList;
    }

    // 배열을 나눠주는 함수
    // 나눈 배열을 합쳐주는 함수에 넣어서 리턴 값으로 정렬된 배열을 줍니다. 
    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> datalist){
        if (datalist.size() <= 1) {
            return datalist;
        }
        int mid = datalist.size() /2;
        ArrayList<Integer> leftData = new ArrayList<Integer>();
        ArrayList<Integer> rightData = new ArrayList<Integer>();
        leftData = this.mergeSplitFunc(new ArrayList<Integer>(datalist.subList(0,mid)));
        rightData = this.mergeSplitFunc(new ArrayList<Integer>(datalist.subList(mid,datalist.size())));
        return this.mergeFunc(leftData, rightData);
    }
}