본질의 중요성

분할 정복법 (Divide and Conquer)

아래 3가지 단계를 거쳐서 어떤 문제를 해결하는 기법

Merge Sort와 Quick Sort에서 사용하는 기법

• 분할(Divide) : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복(Conquer) : 각각의 작은 문제를 순환적으로 해결
• 합병(Merge): 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

Merge Sort

Step 1) Divide - 데이터가 저장된 배열을 절반으로 나눔

Step 2) Recursively sort - 각각을 순환적으로 정렬

Step 3) Merge - 정렬된 두 개의 배열을 합쳐 전체를 정렬

Step 3인 Merge 과정 자세히 보기 

- 정렬된 두 배열을 Merge하는 과정

- 새로운 추가 배열 필요

- i(첫번째 list에서 가장 작은 값), j(두번째 list에서 가장 작은 값), k(추가 list에서 가장 작은 값) 변수 필요

1. A[i]와 A[j]를 비교하여 작은 값을 추가 배열에 추가

2. 작은 값에 속한 인덱스 올림. i++ or j++ , k++

3. i or j가 해당 배열의 인덱스보다 크다면 다른 배열의 값은 그대로 추가배열에 추가 해주면 됨!

소스

// 재귀 함수이므로 매개변수 명시화 필요
public void mergeSort(int[] arr, int p, int r) {		
	if (p < r) {
		int q = (p+r) / 2;		// 1. p와 r의 중간 지점 계산
		mergeSort(arr, p, q);	// 2. 전반부 정렬
		mergeSort(arr, q+1, r);	// 3. 후반부 정렬
		merge(arr, p, q, r);	// 4. 합병
	}
}

/* Merge Business Logic - 정렬되어 있는 두 배열 arr[p...q]와 arr[q+1...r]을 합하여 
 * 정렬된 하나의 배열 arr[p...r]을 만듦. 
 * arr[p... q] arr[q+1...r] => 정렬되어 있는 두 배열 
 * arr[p.................r] => 정렬된 하나의 배열을 만드는 작업 : Merge
 */
public void merge(int[] arr, int p, int q, int r) {
	int i=p, j=q+1, k=p;
	int[] temp = new int[arr.length];
	
	// 각각 i, j가 각 배열의 길이를 넘지 않는다면 비교하여 temp에 넣어주기 
	while(i <= q && j <= r) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		} else {
			temp[k++] = arr[j++];
		} 
	}
	
	// 첫번째 배열에 있는 나머지 값들은 이미 정렬된 데이터들이므로 차례대로 temp 배열에 넣어주면 됨. 
	while (i <= q) {
		temp[k++] = arr[i++];
	}
	
	// 두번째 배열에 있는 나머지 값들은 이미 정렬된 데이터들이므로 차례대로 temp 배열에 넣어주면 됨. 		
	while(j <= r) {
		temp[k++] = arr[j++];
	}
	
	// index p부터 r까지 원래 배열에 값 넣기 
	for (int l = p; l <= r; l++) {
		arr[l] = temp[l];
	}
	
	print(arr);
}

시간복잡도 T(n) = O(nlogn)

if n = 1      -> 0

otherwise -> T(n/2) + T(n/2) + n = 2T(n/2) + n

Ref. https://www.youtube.com/watch?v=2YvFRAC8UTM

Insertion Sort(삽입 정렬) 란?

아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식

Insertion 단계

- item to insert 전의 데이터들은 정렬이 되있는 상태

- item to insert를 정렬 데이터들의 뒤부터 비교하는 것이 효율적! -> 배열에 저장되어있기 때문

public void insertSort(int[] arr) {
	if (arr.length == 0) {
		return;
	}
	
	System.out.print("[정렬할 원소] ");
	print(arr);
	
	for (int i=1; i<arr.length; i++) {		// 1
		for (int j=i-1; j>=0; j++) {
			int temp = arr[i];
			
			// 2
			if (arr[i] > arr[j]) {
				arr[j+1] = temp;
				break;
			}
			
			arr[j+1] = arr[j];		
		}
		

		System.out.print(i + "단계 : ");
		print(arr);
	}
}

실행시간

1번의 for 루프는 n-1번 반복

2번의 삽입은 최악의 경우 i-1번 비교

최악의 경우 시간복잡도:  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ

서로 이웃한 데이터들을 비교하여 가장 큰 데이터를 가장 뒤에 보내며 정렬하는 방식

가장 큰 값을 마지막으로 보내는 개념은 selection sort와 유사

public void bubbleSort(int[] arr) {
	if (arr.length == 0) {
		return;
	}
	
	System.out.print("[정렬할 원소] ");
	print(arr);
	
    	// 뒤에서부터 정렬하므로 last pointer는 정렬된 데이터 앞을 가리킴
	for (int last=arr.length-1; last>=0; last--) {	 // 1
		for (int i = 0; i <= last-1; i++) {	 // 2
			if (arr[i] > arr[i+1]) {
				swap(arr, i, i+1);	 // 3
			}
		}
		
		System.out.print(arr.length - last + "단계 : ");
		print(arr);
	}
}

실행시간

1번의 for 루프는 n-1번 반복

2번의 for 루프는 각각 n-1, n-2, ..., 2, 1번 반복

3번의 교환은 상수 시간 작업

시간복잡도:  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ

배열 중 가장 큰 원소를 오른쪽부터 채워가며 숫자를 정렬하는 방법

각 루프마다

- 최대 원소 찾기

- 최대 원소 <-> 맨 오른쪽 원소 교환

- 맨 오른쪽 원소 제외

public void selectionSort(int[] arr) {
	if (arr.length == 0 ) {
		return;
	}
	
    	System.out.print("[정렬할 원소] ");
	print(arr);
    
	int max;
	
	for (int last = arr.length-1; last>0; last--) { // 1
		max = last - 1;
		
		// 마지막을 제외한 나머지 element 중 가장 큰 수 찾기
		for (int k = last-1; k >= 0; k--) {		// 2
			if (arr[k] > arr[max]) {
				max = k;
			}
		}
		
		if (arr[max] > arr[last] ) {	
			swap(arr, max, last);		// 3
		}
		
		System.out.print(arr.length - last + "단계 : ");
		print(arr);
	}

}

실행 시간

1번의 for 루프 n-1 번 반복

2번에서 가장 큰 수를 찾기 위한 비교 횟수: n-1, n-2, ..., 2, 1

3번의 교환은 상수시간 작업

시간 복잡도: T(n) = (n-1)+(n-2)+...+2+1 = n(n-1)/2 = O(n^2)

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ