글 읽기 - 퀵소트 시간초과라고 나옵니다..

dubu4050 4년 전 0

버블소트로는 해결이 되는데 퀵소트로는 시간초과라고 뜨네요...

퀵소트의 pivot이 제일 앞의 원소를 가리켜서 최악인 N^2의 시간복잡도가 나온다고 생각해도

버블소트가 통과가 되는데 퀵소트가 왜 막히는지 잘 모르겠습니다

어디에서 틀렸는지 알려주시면 감사하겠습니다ㅠㅠ

#include <stdio.h>

int data[1001];

void quickSort(int start, int end){
	if (start >= end)
		return;
	int key = start;
	int i = start + 1;
	int j = end;
	int temp;
	
	while(i<=j){
		while(i <= end && data[i] <= data[key]){
			i++;
		}
		while(j > start && data[j] >= data[key]){
			j--;
		}
		
		if(i > j){
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
		
		quickSort(start, j-1);
		quickSort(j+1, end);
		
	}
	
}

void bubbleSort(int T)
{
    int i, j;
    int temp;
    for (i = 0;i < T;i++)
    {
        for (j = 0;j <T-(i+1);j++)
        {
            if (data[j] > data[j + 1])
            {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}
 
int main(){
	int T;
	int sum = 0;
	
	scanf("%d",&T);
	
	for(int i=0;i<T;i++)
		scanf("%d", &data[i]);
		
	bubbleSort(T);
//	quickSort(0, T-1);	

	
	
	 for (int i = 0; i < T; i++)
        for (int j = 0; j <= i; j++)
            sum += data[j];
	printf("%d",sum);
	return 0;
}

djm03178 4년 전 1

재귀호출의 위치가 잘못되었습니다.

32, 33번째 줄을 35번째 줄의 중괄호 바깥으로 빼주면 됩니다.

dubu4050 4년 전 0

덕분에 해결했습니다! 한참을 고민했네요..

정말 감사합니다ㅠㅠ

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

문제

문제

출처

ICPC

퀵소트 시간초과라고 나옵니다..

dubu4050 4년 전 0

djm03178 4년 전 1

dubu4050 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말