글 읽기 - QuickSort를 구현해봤는데 시간초과가 나옵니다.

upsk1 4년 전 0

시간을 더 단축 시킬 수 있는 방법이 있나요?

#include <iostream>
using namespace std;
void quicksort(int *arr, int left, int right) {
	int p = arr[left], l = left, r = right;
	while (left < right) {
		while (arr[right] >= p && (left < right))right--;
		if (left != right)arr[left] = arr[right];
		while (arr[left] <= p && (left < right))left++;
		if (left != right)arr[right--] = arr[left];
	}
	arr[left] = p;
	if (l < left)quicksort(arr, l, left - 1);
	if (r > left)quicksort(arr, left + 1, r);
}
int a[1000001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	quicksort(a, 0, n - 1);
	for (int i = 0; i < n; i++)cout << a[i] << '\n';
}

jung2381187 4년 전 1

퀵소트를 안 쓰면 됩니다.

퀵소트의 시간복잡도를 찾아보세요.

upsk1 4년 전 0

감사합니다

chogahui05 4년 전 0

뎁스가 깊어지면 heap sort 돌리거나 merge 쓰세요.

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

문제

문제

출처

ICPC

QuickSort를 구현해봤는데 시간초과가 나옵니다.

upsk1 4년 전 0

jung2381187 4년 전 1

upsk1 4년 전 0

chogahui05 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말