[C] 백준 11650번 : 좌표 정렬하기

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

---

문제 접근

 1. 구조체 배열에 값을 입력 받는다.

 2. 합병정렬을 이용해서 정렬한다.

느낀점

 처음에 쉘 정렬을 통해서 정렬해보려고 했지만 시간초과가 나서 좀 더 빠른 정렬 방법이 필요했다. C에서 지원하는 qsort를 사용해보려고 했지만 구조체를 통해서 구현했기 때문에 다소 어려워 시간이 걸렸다. 최후의 방법으로 합병 정렬을 통해서 구현했는데 개념적인 부분만 알고있지 실제로 구현해보기는 처음이다. 이번 기회로 합병 정렬에 대한 이해가 확실히 잡혔다.

코드

#include <stdio.h>

typedef struct {
	int x;
	int y;
}point;

point arr[100001];
point sorted[100001];

void merge(point arr[], int start, int mid, int last) {
	int i, j, k;
	i = start;
	j = mid + 1;
	k = start;

	while (i <= mid && j <= last) {
		if (arr[i].x < arr[j].x)
			sorted[k++] = arr[i++];
		else if (arr[j].x < arr[i].x)
			sorted[k++] = arr[j++];
		else {
			if (arr[i].y < arr[j].y)
				sorted[k++] = arr[i++];
			else if (arr[j].y < arr[i].y)
				sorted[k++] = arr[j++];
		}
	}

	if (i <= mid) {
		while (i <= mid) {
			sorted[k++] = arr[i++];
		}
	}
	else {
		while (j <= last) {
			sorted[k++] = arr[j++];
		}
	}

	for (int i = start; i <= last; i++) {
		arr[i] = sorted[i];
	}
}

void merge_sort(point arr[], int start, int last) {
	int mid;
	if (start < last) {
		mid = (start + last) / 2;
		merge_sort(arr, start, mid);
		merge_sort(arr, mid + 1, last);
		merge(arr, start, mid, last);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n;i++) {
		scanf("%d %d", &arr[i].x, &arr[i].y);
	}

	merge_sort(arr, 0, n - 1);

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

	return 0;
}