글 읽기 - [c언어] 시간초과

angela0102 5년 전 0

퀵정렬로 문제를 풀었는데, 시간초과라고 나옵니다...ㅠㅠ

#include <stdio.h>
//QuickSort - 정가운데pivot. pivot보다크면오른쪽/작으면왼쪽
int a[1000000];
void swap(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
void quickSort(int left, int right) {
	int l = left, r = right;
	int p_num = (left + right) / 2;
	int pivot = a[p_num];
	swap(&a[p_num], &a[left]);
	p_num = left;
	while (l <= r) {
		while (a[l] < pivot)
			l++;
		while (a[r] > pivot)
			r--;
		if (l < r) {
			swap(&a[l], &a[r]);
			l++; r--;
		}
	}
	swap(&a[p_num], &a[r]);
	if (left < r)
		quickSort(left, r);
	if (l < right)
		quickSort(l, right);
}
int main() {
	int n;
	scanf("%d", &n);
	int i = 0;
	//int *a = (int*)malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	quickSort(0, n-1);
	for (i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
	return 0;
}

naive한 퀵소트는 항상 최악의 경우 O(N^2)이 걸린다는 것을 고려해야 하고, 특히 온라인 저지의 입력 데이터에는 이런 케이스가 들어있을 가능성이 아주 높습니다. 그냥 이미 정렬이나 역정렬된 상태의 입력을 주면 되기 때문이죠. 정렬 기능을 직접 구현하는 게 목표라면 병합 정렬이나 힙 정렬, 아니면 좀 더 보완된 퀵 정렬 등을 구현하셔야 합니다. 아니면, 그냥 stdlib.h에 있는 qsort 쓰세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c언어] 시간초과

angela0102 5년 전 0

jh05013 5년 전 1

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말