[알고리즘/병합정렬(Merge Sort)] -자바

 

 

 

병합정렬에 대해 알아보자

‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법입니다.

O(NlogN)을 보장해요.

일단 반으로 나누고 보는거에요.

 

이런식으로 저장이 될텐데요.

처음에 정렬되어있지 않은 배열을 가장 작게 쪼갠 뒤에 합치면서 정렬하는 거에요.

 

여기서 어떻게 정렬해서 들어가는지 궁금하시죠? 저는 궁금했거든요 ㅎ

두개는 지금 떨어져있지만 메모리상에서는 붙어있는 것과 같습니다. 그래서 index를 x,mid,y로 구분해준 뒤에 x는 mid로 접근하고 mid에서 y로 접근하면서 값을 비교해서 배열에 넣어가면서 정리하면 됩니다. 그럼결국 N번만에 가능하잖아요??

 

 

코드

public class 분할정렬 {
	
	static int[] sorted = new int[8];
	
	public static void main(String[] args) {
		
		int[] arr = {8,5,3,2,1,7,3,4};
		mergeSort(arr, 0, arr.length-1);
		
		for(int z:arr) {
			System.out.print(z+" ");
		}
		
		
	}
	
	public static void merge(int[] arr,int x,int mid,int y) {
		
		int i = x;
		int j = mid+1;
		int k = x;
		
		//작은거 부터 넣어주기
		while(i<=mid && j<=y) {
			if(arr[i]<=arr[j]) {
				sorted[k] = arr[i];
				i++;
			}else {
				sorted[k] = arr[j];
				j++;
			}
			k++;
		}
		
		//나머지 넣어주기
		if(i>mid) {
			for(int t=j;t<=y;t++) {
				sorted[k] = arr[t];
				k++;
			}
		}else {
			for(int t=i;t<=mid;t++) {
				sorted[k] = arr[t];
				k++;
			}
		}
		//원래 배열에 넣어주기
		for(int t=x;t<=y;t++) {
			arr[t] = sorted[t];
		}
	}
	
	public static void mergeSort(int[] arr,int x,int y) {
		//값이 1보다 커야
		if(x<y) {
			int mid = (x+y)/2;
			mergeSort(arr, x, mid);
			mergeSort(arr, mid+1, y);
			merge(arr, x, mid, y);
		}
	}

}

코드설명

코드설명은 따로 필요없을 것 같고 코드내에 주석참고하시면 됩니다.

 

 

 

동빈나님 유튜브보고 공부했습니다.