글 읽기 - 퀵정렬을 사용했는데 시간초과가 납니다..

dlgpdus1117 5년 전 0

버블정렬을 써서 시간초과가 나와서 퀵정렬을 이용해보았는데 여전히 시간초과가 발생합니다.

#define _CRT_SECURE_NO_WARNINGS
#include
struct Point
{
int x;
int y;
};
void Swap(Point arr[], int idx1, int idx2)
{
Point temp;
temp.x = 0; temp.y = 0;

temp.x = arr[idx1].x;
arr[idx1].x = arr[idx2].x;
arr[idx2].x = temp.x;

temp.y = arr[idx1].y;
arr[idx1].y = arr[idx2].y;
arr[idx2].y = temp.y;
}

int Partition(Point arr[], int left, int right)
{
Point pivot;
pivot.x = arr[left].x; 
pivot.y = arr[left].y;
int low = left + 1;
int high = right;

while (low <= high) 
{ 
while((pivot.x >= arr[low].x)&& (pivot.y>=arr[low].y) && low <= right)
low++;

while((pivot.x <= arr[high].x) &&(pivot.y <= arr[high].y)&& high >= (left+1))
high--;

if (low <= high) 
Swap(arr, low, high); 
}

Swap(arr, left, high); 
return high; 
}

void QuickSort(Point arr[], int left, int right)
{
if (left <= right)
{
int pivot = Partition(arr, left, right); 
QuickSort(arr, left, pivot - 1); 
QuickSort(arr, pivot + 1, right); 
}
}

int main() {
int num = 0;
Point point[100000];
scanf("%d", &num);
if (num < 1 || num>100000) return 0;

for (int i = 0; i < num; i++) {
scanf("%d %d", &point[i].x, &point[i].y);

}

QuickSort(point, 0, num-1);

for (int i = 0; i < num; i++) {
printf("%d %d\n", point[i].x, point[i].y);
}
return 0;
}

kimsy96 5년 전 0

퀵정렬도 최악의 경우 O(n^2)으로 동작합니다.

boj데이터가 빡세서 퀵정렬을 직접만든경우 시간초과나는 경우를 더러 봤습니다.

c언어의 내장함수를 쓰시던지 아니면 다른 정렬을 써보세요

zlzmsrhak 5년 전 0

피봇을 가장 왼쪽으로 정하면 오름차순일때 N^2이 됩니다.

2. 피봇을 랜덤으로 잡아도 모든 원소가 같으면 경우에 따라 N^2이 될 수도 있습니다.

chogahui05 5년 전 0

Tip. Quick sort에서 depth가 증가하면 Heap sort로 돌리는 방법도 좋은 방법입니다. 아니면 Merge를 쓰거나..

apjw6112 5년 전 0

c정렬함수를 쓰세요

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

문제

문제

출처

ICPC

퀵정렬을 사용했는데 시간초과가 납니다..

dlgpdus1117 5년 전 0

kimsy96 5년 전 0

zlzmsrhak 5년 전 0

chogahui05 5년 전 0

apjw6112 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말