[알고리즘] 백준 2751번 문제_1000만개 정렬

1000만개 정렬 : https://www.acmicpc.net/problem/2751

================================== 풀이 ====================================

​

퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬

int data[1000000];

void quickSort(int *data, int start, int end) {

	if (start >= end) {
		return;
	}

	int key = start, st = start + 1, ed = end, tmp;

	while (st <= ed) {
		while (data[key] >= data[st] && st <= end) 
			st++;

		while (data[key] <= data[ed] && ed > start)
			ed--;

		if (st > ed) {
			tmp = data[key];
			data[key] = data[ed];
			data[ed] = tmp;
		}
		else {
			tmp = data[st];
			data[st] = data[ed];
			data[ed] = tmp;
		}
	}
	quickSort(data, start, ed - 1);
	quickSort(data, ed + 1, end);
}

int main(void) {
	
	int num;

	scanf("%d", &num);
	for (int i = 0; i < num; i++)
		scanf("%d", &data[i]);

	quickSort(data, 0, num - 1);

	for (int i = 0; i < num; i++)
		printf("%d\n", data[i]);
}

※ 위 코드는 코드상 문제는 없지만 5 4 3 2 1 의 경우 최악의 경우로 N ^ N의 시간 복잡도를 가지고 있기때문에 실제로 해당 방법으로

코딩할 경우 시간 초과로 안되는 것을 확인하였다.

추후 알고리즘을 더 공부하여 추가할 예정