문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

접근 방법

좌표를 구조체로 정의하고 구조체 포인터에 메모리를 동적할당해서 입력값을 채워준다. 그렇게 채워진 값을 토대로 버블정렬을 해봤지만 시간초과로 실패했다. 더 빠른 정렬인 퀵소팅 정렬을 사용해서 문제를 해결할 수 있었다.

퀵소팅 알고리즘

무시무시한 재귀 알고리즘이다! 코드를 분석해본 결과 엉덩이 무거운 left, right, pivot 인덱스와 while속에서 빨빨움직이는 i 와 j인덱스가 있었다.재귀를 호출하는 main에선 sort(left, right, array)정도로 호출하는데, 이때 left, right는 배열 array의 양 끝단 인덱스값을 넣어준다.pivot = left, j = pivot, i = left + 1;일단 변수 pivot은 매개변수 left를 받아준다. 피봇이 가리키는 값과, 그 다음값들을 순차적으로 비교해서 스왑해준다. 이때 스왑을 피봇이 가리키는값을 직접 바꿔주는게 아니라, 특이하게 피봇 바로 다음인덱스의 값과 바꿔준다(j++). 스왑이 발생해야 할 때마다 그 다음 인덱스, 그 다음 인덱스(j++)로 스왑해주고, 피봇인덱스와 그에 해당하는값은 루프가 끝날때까지 움직이지 않는다. 루프가 한바퀴 다 끝나면 array[left]와 array[j]를 바꿔주고 pivot = j를 받게 하는데 이렇게 되면 이제 피봇값을 기준으로 그보다 작은값과 큰값으로 갈라지게 된다. 물론 정렬은 안된 상태로. 이제 여기서 분할 정복이 묘수를 부리는데, 재귀를 이런식으로 호출한다.

sort(left, pivot - 1, array)
sort(pivot + 1, right, array)

이렇게 하게 되면, 일단 기존의 루프로 인해 한차례 pivot값 기준으로 정렬된 상태의 배열을 다시 0 ~ 기존 기준값 피봇인덱스 직전까지 한차례 정렬하게 되고, 이를 반복함으로써 최초의 기준이전의 값들은 정렬된 상태가 되게된다. 분할해서 정복한것이다. 이제 나머지를 정복해야할 차례고, 나머지는 최초의 피봇 이후의 값부터 끝까지를 정렬하면 되므로 sort(pivot + 1, right, array)가 되는것이다.

#include <stdio.h>
#include <stdlib.h>

typedef struct	t_point
{
int	x;
int	y;
}	s_point;

void	swap(s_point *a, s_point *b)
{
int x;
int y;

x = a->x;
y = a->y;
a->x = b->x;
a->y = b->y;
b->x = x;
b->y = y;