글 읽기 - 2751 퀵정렬

neity16 4년 전 0

다른분들처럼 일반 퀵정렬을 사용하였는데 시간초과가 뜨네요 뭐가 다른가요..?

#include <iostream>

using namespace std;

int number, dat[1000001];

void quicksort(int* dat, int start, int end) {

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

int main()
{
	cin >> number;
	for (int i = 0; i < number; i++)
		cin >> dat[i];
	quicksort(dat, 0, number - 1);
	for (int i=0;i<number;i++)
	{
		cout << dat[i];
		if (i != number - 1)
			cout << '\n';
	}
}

djm03178 4년 전 0

다른 분들도 그냥 퀵소트를 썼으면 시간 초과가 납니다.

https://www.acmicpc.net/board/...

sait2000 4년 전 0

O(N^2)인 것과는 별개로, 예제는 나오나요? dat이 0으로 초기화되어있고, 17~20에서 i가 end 내지 j를 넘는 걸 막는 코드가 없으니까 예제를 넣어보면 i가 dat 끝까지 넘어갑니다. 19번 줄에서 i를 출력해보시면 아실 겁니다.

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

문제

문제

출처

ICPC

2751 퀵정렬

neity16 4년 전 0

djm03178 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말