[C] 백준 10814번 : 나이순 정렬

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

10814번: 나이순 정렬

---

문제 접근

 1. 구조체를 정의한다. 구조체는 파이썬의 dictionary와 비슷한 타입으로 만든다. 

 2. 합병정렬을 이용한다. 이 때, 나이만 비교하는데 나이가 같다면 앞에 오는 순서를 그대로 이어 받는다.

느낀점

 계속된 합병정렬을 응용하는 문제이다. 이전의 문제와 다른 점이라면 stable sort 와 in-place sort의 개념을 잡은 계기가 되었다는 점이다.

 stable sort :  중복된 값을 정렬했을 때 순서가 변하지 않으면 stable, 변하면 unstable 

 // stable sort → insertion sort, merge sort, bubble sort, countin sort

 // unstable sort → selection sort, heap sort, shell sort, quick sort

 in-place sort : 추가적인 메모리 공간을 요구한다면 in-place

 // in-place sort : insertion sort, selection sort, bubble sort, shell sort, heap sort, quick sort

 // not in-place sort : merge sort, counting sort, radix sort, bucket sort

코드

#include <stdio.h>

typedef struct {
	int age;
	char string[101];
} id;

id sorted[100001];
id arr[100001];

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

	while (i <= mid && j <= last) {
		if (arr[i].age < arr[j].age) {
			sorted[k++] = arr[i++];
		}
		else if (arr[i].age > arr[j].age) {
			sorted[k++] = arr[j++];
		}
		else {
			sorted[k++] = arr[i++];
		}
	}
	if (i <= mid) {
		while (i <= mid) {
			sorted[k++] = arr[i++];
		}
	}
	else {
		while (j <= last) {
			sorted[k++] = arr[j++];
		}
	}
	for (k = start; k <= last;k++) {
		arr[k] = sorted[k];
	}
}

void merge_sort(id 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 %s", &arr[i].age, &arr[i].string);
	}

	merge_sort(arr, 0, n - 1);
	
	for (int i = 0; i < n;i++) {
		printf("%d %s\n", arr[i].age, arr[i].string);
	}

	return 0;
}