글 읽기 - C++ 퀵소트로 구현 시간초과

junsik456 2년 전 0

시간초과 뜨는 이유 알 수 있을까요?

그리고 함수인자로 벡터타입 보낼때 참조자로 보내야 하는 이유도 알려주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void quicksort(vector<int>&, int, int);

int main(void)
{

	int N, t;
	vector<int> v;
	cin >> N;
	while (N--)
	{
		scanf("%d", &t);
		v.push_back(t);
	}
	quicksort(v, 0, v.size() - 1);
	for (int i = 0; i < v.size(); i++)
		printf("%d\n", v[i]);

	return 0;
}


void quicksort(vector<int> &v, int start, int end)
{
	if (start >= end)
		return;
	int i = start + 1, j = end;
	while (1)
	{
		while (i <= end && v[i] <= v[start])
			i++;
		while (v[j] >= v[start] && j > start)
			j--;
		if (i > j)
		{
			swap(v[start], v[j]);
			break;
		}
		else
		{
			swap(v[i], v[j]);
		}
	}
	quicksort(v, start, j - 1);
	quicksort(v, j + 1, end);

}

bamgoesn 2년 전 1

퀵소트는 정해진 위치에 피벗을 두고 정렬할 경우 시간복잡도가 O(N^2)인 데이터를 쉽게 만들 수 있습니다. 따라서 일반적인 경우엔 STL sort 함수를 사용하게 됩니다.

정렬 알고리즘 구현을 연습하고자 할 경우엔, 피벗을 랜덤한 위치로 잡는 퀵 정렬을 구현하거나, 병합 정렬과 같이 최악의 경우에도 O(NlogN)인 알고리즘을 사용하면 이 문제를 피할 수 있습니다.

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

문제

문제

출처

ICPC

C++ 퀵소트로 구현 시간초과

junsik456 2년 전 0

bamgoesn 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말