글 읽기 - 제가 퀵소트를 만들어서 풀어보았는데 왜 시간초과가 나는건지 모르겠습니다ㅠ

ysysysy3333 1년 전 0

시간초과의 원인이 무엇인가요? 처음부터 오름차순일때 시간복잡도가 n^2여서 그런건가요?

#include <stdio.h>
void quickSort(int* data, int start, int end){
	if(start >= end){
	return;
	}
	int i = start + 1, key = start;
	int j = end,tmp;
	
	while(i <= j){
			while(i <= end && data[key] >= data[i]){
				i++;
			}
			while(j > start && data[key] <= data[j]){
				j--;
			}
		if(j < i){
			tmp = data[key];
			data[key] = data[j];
			data[j] = tmp;
		}else{
			tmp = data[j];
			data[j] = data[i];
			data[i] = tmp;
		}
	}
	quickSort(data, j + 1, end);
	quickSort(data, start, j - 1);
}
int main()
{
	int n;
	
	scanf("%d",&n);
	
	int data[n];
	
	for(int i = 0; i < n; i++){
		scanf("%d",&data[i]);
	}
	
	quickSort(data, 0, n-1);
	
	for(int i = 0; i < n; i++){
		printf("%d\n",data[i]);
	}
	
}

0000000000 1년 전 0

pivot(위 코드에서의 key)을 무조건 첫 번째 값으로만 잡으면 TLE가 날 수 있습니다. 해결을 위해서는 pivot을 랜덤으로 잡거나 정렬 전에 배열을 섞어 주는 방법(C++의 random_shuffle() 함수가 있습니다) 등이 있습니다.

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

문제

문제

출처

ICPC

제가 퀵소트를 만들어서 풀어보았는데 왜 시간초과가 나는건지 모르겠습니다ㅠ

ysysysy3333 1년 전 0

0000000000 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말