합병정렬 ( MergeSort) Java로 구현하기

MergeSort란?

합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

출처 - 위키

뭐 설명은 여기저기서 다 보면 이해 가능할거라 생각한다.

그럼 자바로 한번 구현해보자.

public static void main(String[] args) {

          int[] arr = {3,2,9,5,10,15,40,1,22,2,99};

mergeSort(arr);

System.out.println("arr: " + Arrays.toString(arr));

}

// 배열들을 크기가 1이 될때 까지 나누는 메소드

public static void mergeSort(int[] arr) {

// 위 법칙에서 1번 적용

if( arr.length == 1 ) return;

// 위 법칙에서 2번 적용

int arrSize = arr.length;

int mid = arrSize/2;

int[] leftArr = new int[mid];

int[] rightArr = new int[arrSize-mid]; //  오른쪽 배열 생성

// 왼쪽 배열에 arr 값을 채워준다

for(int i=0; i<leftArr.length; i++) {

leftArr[i] = arr[i];

}

// 오른쪽 부분에 arr 값을 채워준다.

for(int i=0; i<rightArr.length; i++) {

rightArr[i] = arr[mid+i];    //  i+center 해야 오른쪽 배열이 생성된다.

}

// 위반복을 재귀함수로 반복

mergeSort(leftArr);

mergeSort(rightArr);

// 나눠진 배열들의 수를 비교하며 다시 합쳐준다

sort(leftArr, rightArr, arr);

}

public static void sort(int[] leftArr, int[] rightArr, int[] arr) {

// 3가지 변수를 생성한 이유는 leftArr+rightArr = arr 의 사이즈가 되기 때문이다.

int leftCnt = 0;

int rightCnt = 0;

int totalCnt = 0;

// 반복문을 통해 둘중 하나의 배열이라도 숫자가 같아 질때까지 수행한다.

while( leftArr.length != leftCnt && rightArr.length != rightCnt ) {

if( leftArr[leftCnt] < rightArr[rightCnt] ) {

arr[totalCnt] = leftArr[leftCnt];

totalCnt++;

leftCnt++;

}else {

arr[totalCnt] = rightArr[rightCnt];

totalCnt++;

rightCnt++;

}

}

// 왼쪽배열이 아직 남아 있다면 나머지 값을 합쳐질 배열에 넣는다

while( leftCnt != leftArr.length) {

arr[totalCnt] = leftArr[leftCnt];

totalCnt++;

leftCnt++;

}

// 위와 동일하게 오른쪽 배열 확인

while( rightCnt!= rightArr.length) {

arr[totalCnt] = rightArr[rightCnt];

rightCnt++;

totalCnt++;

}

}

소스 하이라이터는 나중에.....티스토리 귀찮다능...