글 읽기 - 퀵소트 시간초과 질문드립니다

jhko00 3년 전 0

함수로 구현한 퀵소트 부분을 sort()함수로 대체하면 맞고 이대로 제출하면 시간 초과가 납니다

sort()함수도 퀵소트로 구현되어있는 걸로 아는데

제가 구현한 함수 어느 부분이 문제가 되는지 파악이 안되서 질문드립니다

#include <stdio.h>
#include <algorithm>
using namespace std;
pair<int,int> p[1000000];

//퀵소트 구현 함수
void q_sort(pair<int,int> *p, int str, int fin){ //str번부터 fin-1번까지 소트
	int l,h;
	pair<int,int> temp;
	if(str >= fin-1) return; //소트범위가 1이하면 끝냄
	while(1){
        //pivot은 str
        //str+1부터 큰값 탐색
		for(h=str+1;h<fin;h++){
			if(p[h].first > p[str].first) break;
		}
        //fin-1부터 작은값 탐색
		for(l=fin-1;l>str;l--){
			if(p[l].first < p[str].first) break;
		}
        //큰값이 뒤에있는 경우 -> pivot과 작은값 swap
		if(h > l){
			temp=p[str]; p[str]=p[l]; p[l]=temp;
			break;
		}
        //큰값,작은값 swap
		else{
			temp=p[h]; p[h]=p[l]; p[l]=temp;
		}
	}
    //pivot값 기준 좌우 퀵소트
	q_sort(p,str,l);
	q_sort(p,l+1,fin);
}

//메인함수
int main(){
	int n,i,a,b,cur_l,cur_r,ans=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d",&a,&b);
		p[i]=make_pair(min(a,b),max(a,b));
	}
	q_sort(p,0,n);
	cur_l=p[0].first; cur_r=p[0].second;
	for(i=1;i<n;i++){
		if(p[i].first <= cur_r && p[i].second > cur_r){
			cur_r=p[i].second;
		}
		else if(p[i].first > cur_r){
			ans+=cur_r-cur_l;
			cur_l=p[i].first;
			cur_r=p[i].second;
		}
	}
	ans+=cur_r-cur_l;
	printf("%d\n",ans);
	return 0;
}

palilo 3년 전 1

그냥 퀵소트는 최악의 경우에 N^2이 걸립니다.

이 코드같은 경우, p가 오름차순이든 내림차순이든 이미 정렬되어 있는 상태로 주어진다면 복잡도가 N^2이 되겠죠.

sort()함수는 최악의 경우에도 NlogN을 보장해주기 위해 퀵소트와 다른 정렬방식을 섞은 방식으로 구현되어 있습니다.

jhko00 3년 전 0

그렇군요 저는 sort()함수는 퀵소트로만 구현되어 있는줄 알았네요
답변 주셔서 감사합니다

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

문제

문제

출처

ICPC

퀵소트 시간초과 질문드립니다

jhko00 3년 전 0

palilo 3년 전 1

jhko00 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말