글 읽기 - 11650번 quick_sort 구현 오류

karl0905 2년 전 0

quick_sort를 직접 구현했는데 어디서 잘못 된건지 확인이 어렵습니다.

고수님들의 확인 부탁드립니다 ㅠㅠ

#include <iostream>
const int MAX_SIZE = 100001;
int N;
struct Pos
{
	int x;
	int y;
	bool operator<(const Pos& a);
};

bool Pos::operator<(const Pos & a)
{
	if ((this->x < a.x)
		|| ((this->x == a.x) && (this->y < a.y)))
	{
		return true;
	}
	else
	{
		return false;
	}
}
void q_sort(Pos *arr, const int left, const int right)
{
	// 원소가 1개인 경우
	if (left >= right)
	{
		return;
	}
	int pivot_num = (left + right) / 2;
	int lp = left;
	int rp = right;
	Pos & pivot_pos = arr[pivot_num];

	while (lp <= rp)
	{
		while ( arr[lp] < pivot_pos )
		{
			lp++;
		}
		while ( pivot_pos < arr[rp] )
		{
			rp--;
		}
		if (lp <= rp)
		{
			Pos temp = arr[lp];
			arr[lp] = arr[rp];
			arr[rp] = temp; 
			lp++;
			rp--;
		}
	}

	if ( left < rp )
	{
		q_sort(arr, left, rp) ;
	}
	if (lp < right)
	{
		q_sort(arr, lp, right) ;
	}
}
int main()
{
	// input
	scanf(" %d", &N);
	Pos* posArr = new Pos[N];
	for (int i = 0; i < N; ++i)
	{
		scanf(" %d %d", &posArr[i].x, &posArr[i].y);
	}

	// sort
	q_sort(posArr, 0, N - 1);

	// output
	for (int i = 0; i < N; ++i)
	{
		printf("%d %d\n", posArr[i].x, posArr[i].y);
	}
	delete[] posArr;
	return 0;
}

karl0905 2년 전 0

반례 확인용.

1 -1

1 1

-1 1

-1 -1

karl0905 2년 전 0

문제 해결하였습니다.

문제 원인은 pivot 값을 받아올 때, Reference로 받아오는 것이 문제가 되었습니다.

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

문제

문제

출처

ICPC

11650번 quick_sort 구현 오류

karl0905 2년 전 0

karl0905 2년 전 0

karl0905 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말