글 읽기 - c) 쉘 정렬은 통과, 그런데 퀵정렬은 시간초과

mun9769 3년 전 0

쉘정렬과 퀵정렬 함수입니다.

쉘정렬의 결과는 통과했지만 퀵정렬로 했을 때 시간초과가 났습니다.

쉘정렬의 시간복잡도는 O(n^1.5)이고 퀵정렬의 시간복잡도는 O(nlogn)으로

퀵정렬이 쉘정렬보다 더 빠르다고 알고있는데

왜 퀵정렬은 시간초과가 났을까요?

void shell(int *a, int n)
{
	int i, j, h;
	for(h = n/2; h>0; h/=2)
		for(i = h; i<n; i++)
		{
			int tmp = a[i];
			for(j = i-h; j>= 0 && a[j] > tmp; j-= h)
				a[j+h] = a[j];
			a[j+h] = tmp;
		}
}


void quick(int *a, int left, int right)
{
	int pl = left;
	int pr = right;
	int x = a[(pl+pr) /2];
	do {
		while(a[pl] < x) pl++;
		while(x < a[pr]) pr--;
		if(pl <= pr) {
			swap(int,a[pl],a[pr]);
			pl++;
			pr--;
		}
	}while(pl<=pr);
	if(left < pr) quick (a,left,pr);
	if(pl<right) quick(a,pl,right);
}

djm03178 3년 전 1

https://www.acmicpc.net/board/... 를 참고하세요.

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

문제

문제

출처

ICPC

c) 쉘 정렬은 통과, 그런데 퀵정렬은 시간초과

mun9769 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말