글 읽기 - 버블정렬과 qsort 속도 차이?

cdm05162 1년 전 0

제출을 하게 되면 시간초과가 나오게 되는데 정렬하는 부분에서 시간을 더 사용해서 그런건가요?

#include <stdio.h>
#include <stdlib.h>
int binary_search(int *own,int n,int num)
{
    int start = 0;
    int end = n;
    int mid = (start + end ) / 2;
    while (start <= end )
    {
        if ( own[mid] == num )
            return 1;
        else if ( own[mid] < num )
            start = mid + 1;
        else
            end = mid - 1;
        mid = ( start + end ) / 2;
    }
    return 0;
}
int main()
{
	int n = 0, m = 0;
	int own[500001] = { 0, };
	int card[500001] = { 0, };
	int temp = 0;
	
	scanf("%d", &n);
	for( int i = 0; i < n; i++ ) scanf("%d", &own[i]);
	scanf("%d", &m);
	for( int i = 0; i < m; i++ ) scanf("%d", &card[i]);

	// 배열값 정렬 후 비교
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n - 1 - i; j++){
			if(own[j] > own[j + 1]){
				temp = own[j];
				own[j] = own[j + 1];
				own[j + 1] = temp;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n - 1 - i; j++){
			if(card[j] < card[j + 1]){
				temp = card[j];
				card[j] = card[j + 1];
				card[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < m; i++ )
    {
        if ( binary_search ( own, n, card[i] ) )
            printf("1 ");
        else
            printf("0 ");
    }
	
	return 0;
}

0000000000 1년 전 0

버블 정렬은 시간복잡도가 O(N^2)인 반면 qsort에서 사용하는 정렬은 시간복잡도가 O(NlogN)입니다.

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

문제

문제

출처

ICPC

버블정렬과 qsort 속도 차이?

cdm05162 1년 전 0

0000000000 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말