글 읽기 - 버블소트로는 시간초과를 잡을 방법이 없나요?

jks961616 7년 전 0

이게 제 코드입니다. 제목에서 아시겠지만 버블소트를 사용하였습니다.

그런데 버블소트를 사용하니 시간초과가 나오더군요.

버블 소트를 이용하였을때 시간초과에 걸리지 않는 방법이 있나요?

#include <stdio.h>

void sort(int *i, int *j)
{
	int temp;
	
	temp = *i;
	*i = *j;
	*j = temp;
}

int main(void)
{
	int n, i, j;
	int num[1000000];

	scanf("%d", &n);

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

	for(i = n - 1 ; i > 0 ; i--)
		for(j = 0 ; j < i ; j++)
			if(num[j] > num[j+1])
				sort(&num[j], &num[j+1]);


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

orange4glace 7년 전 0

버블소트는 시간복잡도가 N²이라 힘들것같아요ㅠㅠ

nisroeld99 7년 전 0

nlogn 정렬 공부해보세요

yclock 7년 전 0

이 문제는 다른 정렬 문제와 다르게 특수한 조건이 있기 때문에,

O(N)만에 풀 수 있습니다.

버블소트 등과 같은 정렬 알고리즘은 O(N²)이기 때문에, N의 최대값이 10⁶인 이 문제를 시간 안에 풀기는 어렵습니다.

퀵소트나 Merge Sort같은 O(N log N) 알고리즘을 공부해보시기 바랍니다.

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

문제

문제

출처

ICPC

버블소트로는 시간초과를 잡을 방법이 없나요?

jks961616 7년 전 0

orange4glace 7년 전 0

nisroeld99 7년 전 0

yclock 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말