병합 정렬

• 배열을 두 개로 쪼개어서 정렬을 한 뒤, 다시 병합하는 작업을 반복하는 정렬 알고리즘
• 분할 정복 방법
  • 주어진 문제의 해를 구하기 시작
  • 그 문제를 여러 개의 작은 부문제들로 나누어
  • 각 부문제의 해를 구한 다음
  • 그 해들을 종합해서 원래 문제의 해를 구하는 방법
• O(nlogn)

• 최소 단위(1개)로 분할

void MergeSort( int arg[], int left, int right) {
	int mid;
	if ( left < right ) {
		mid = ( left + right ) / 2;
		MergeSort(arg, left, mid);
		MergeSort(arg, mid + 1, right);
		Merge(arg, left, mid+1, right);
	}
}

• 정렬된 2개 단위를 병합하여 정렬
• 정렬된 각 부분의 1개씩 비교
• 남은 부분은 뒤쪽으로 이동

// 병합정렬 병합/합병 함수 
void Merge(int arr[], int left, int mid, int right) {
	int temp[10] = { 0, };
	int index = left;
	int low = left;
	int high = mid;

	while ((low < mid) && (high <= right)) {
		if (arr[low] < arr[high]) {
			temp[index] = arr[low];
			low++;
		}
		else {
			temp[index] = arr[high];
			high++;
		}
		index++;
	}

	if (low < mid) {
		for (low = low; low < mid; low++, index++) {	// 앞쪽 배열에 남은것 모두 가져오기
			temp[index] = arr[low];
		}
	}
	if (high <= right) {
		for (mid = high; mid <= right; mid++, index++) {	// 뒤쪽 배열에 남은것 모두 가져오기
			temp[index] = arr[mid];
		}
	}

	for (index = left; index <= right; index++) {
		arr[index] = temp[index];
	}
	Display(arr, 10);
}

퀵 정렬

• 분할 정복 방법

• O(nlogn)

• 적절한 원소 하나를 기준으로 기준보다 작은 것, 큰 것으로 나눈다.

// 퀵 정렬 함수 
void QuickSort(int arg[], int left, int right) {
	int pivot = 0;

	if (left <= right) {
		pivot = QuickPartition(arg, left, right);	// 퀵 분할
		QuickSort(arg, left, pivot - 1);		// 피벗보다 왼쪽 영역 정렬
		QuickSort(arg, pivot + 1, right);		// 피벗보다 오른쪽 영역 정렬
	}
}