[11] 심화 정렬 ( SORT )

분할 정복법(divide and conquer) : Merge Sort, Quick Sort

분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

정복 : 각각의 작은 문제를 순환적으로해결

 

Merge Sort 

Merge ( 합병 ) : 작은 문제의 해를 합해서 원래 문제에 대한 해를 구함

 

 

 

https://gmlwjd9405.github.io/images/algorithm-merge-sort/merge-sort-concepts.png

 

 

// 합병정렬 

public class sort_1 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); // 배열 크기
		int[] arr = new int[n];
		
		for(int i =0; i<n;i++)
		{
			arr[i]= scanner.nextInt();
		}
		arr = MergeSort(arr, 0, arr.length-1);
		
		for(int i=0;i<n;i++) System.out.println(arr[i]);
		
	}
	
	static int[] MergeSort(int[] arr,int i, int j) { 
		
		int mid;
		if(i<j) {
			mid = (i+j)/2;
            
            // 분할부분
			MergeSort(arr,i,mid); 
			MergeSort(arr, mid+1, j);
            
            // 정복부분
			Merge(arr, i, mid, j);
		}
		return arr;
		
	}

	static void Merge(int[] arr,int f , int mid, int l) {
		int i = f;
		int j = mid+1;
		int k=f;
		int[] temp = new int[arr.length];
		
		while(i<=mid && j<=l ) {
			if(arr[i]<arr[j]) {
				temp[k] =arr[i];
				i++;
			}
			else {
				temp[k]=arr[j];
				j++;
			}
			k++;
		}
		
		if(i>=mid) {
			while(j<=l) {
				temp[k]=arr[j];
				j++;
				k++;
			}
		}
		if(j>=l) {
			while(i<=mid) {
				temp[k]=arr[i];
				i++;
				k++;
			}
		}
		
		for(int a=f; a<=l; a++){
		    arr[a] = temp[a];
		 }
	}
}

 

재귀함수가 너무 어려워서 참고한 영상 ! 

https://www.youtube.com/watch?v=FCAtxryNgq4