분할정복법에서의 정렬, 퀵정렬과 합병정렬 [C]

분할정복법이란
여러알고리즘의 기본이 되는 해결방법이다
엄청나게 크고 방대한 문제를 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념이다.

분할정복법에서의 정렬방법에는 대표적으로 퀵정렬과 합병정렬이 있다.

##퀵정렬을 알아보자
퀵정렬은 매우 빠른 수행 속도를 자랑하는 정렬방법이다.
전체리스트를 2개의 부분리스트로 분할하고, 각가의 부분리스를 다시 퀵정렬하는 전형적인 분할 정복법을 사용한다.

퀵정렬코드이다

#include <stdio.h>
#define swap(x,y,t) ((t)=(x), (x)=(y), (y)=(t))

int n, cnt;

void print(int list[]) {
	printf("%d?④퀎 : ", ++cnt);
	int i;
	for(i=0; i<n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");
}

int quick(int list[], int left, int right) {
	int low=left, high=right+1, pivot=list[left], temp;
	while(1) {
		while(1) {
			low++;
			if(list[low] > pivot) break;
		}
		while(1) {
			high--;
			if(list[high] < pivot || high==left) break;
		}
		if(low<high) {
			swap(list[low], list[high], temp);
		} else break;
	}
	swap(list[high], list[left], temp);
	print(list);
	return high;
}

void sort(int list[], int left, int right) {
	if(left < right) {
		int mid = quick(list, left, right);
		sort(list, left, mid-1);
		sort(list, mid+1, right);
	}
}

int main() {
	scanf("%d", &n);
	int arr[n];
	int i;
	for(i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr, 0, n-1);
	return 0;
}

##합병정렬을 알아보자
합병정렬은 매우 빠른 수행 속도를 자랑하는 정렬방법이다.
하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다.

합병정렬코드이다

#include <stdio.h>

int cpy[100], cnt, n;

void print(int list[]) {
	printf("%d?④퀎 : ", ++cnt);
	for(int l=0; l<n; l++) {
		printf("%d ", list[l]);
	}
	printf("\n");
}

void merge(int list[], int left, int mid, int right) {
	int i=left, j=mid+1, k=left;
	while(i<=mid && j<=right) {
		if(list[i]>list[j]) {
			cpy[k++] = list[j++];
		} else {
			cpy[k++] = list[i++];
		}
	}
	int l;
	if(mid<i) {
		for(l=j; l<=right; l++) cpy[k++] = list[l];
	} else {
		for(l=i; l<=mid; l++) cpy[k++] = list[l];
	}
	for(l=left; l<=right; l++) {
		list[l] = cpy[l];
	}
	print(list);
}

void sort(int list[], int left, int right) {
	if(left< right) {
		int mid = (left+right)/2;
		sort(list, left, mid);
		sort(list, mid+1, right);
		merge(list, left, mid, right);
	}
}

int main() {
	scanf("%d", &n);
	int list[n];
	for(int l=0; l<n; l++) {
		scanf("%d", &list[l]);
	}
	sort(list, 0, n-1);
}