10월 12일(수) - 정렬(10814번 *풀이진행중)

정렬 - 10814번

10814번: 나이순 정렬

 

문제점

1. stable sort 를 활용하라는 뜻이라서 merge sort를 활용해서 풀이를 진행했다

-> "틀렸습니다"만이 나오면서 merge sort를 활용하는 것에 대한 의문이 생김

2. 

 

 

1차풀이

(이전 문제들처럼 merge sort를 활용해서 풀이했으나, "틀렸습니다"만이 나옴)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

typedef struct {
	int age;
	char name[100];
}array;

array name_set[100000];
array sorted[100000];

void merge(array* list, int left, int mid, int right)
{
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right)
	{
		if (list[i].age < list[j].age)
		{
			sorted[k++] = list[i++];
		}
		else if(list[i].age > list[j].age)
		{
			sorted[k++] = list[j++];
		}
		else
		{
			if (list[i].age == list[j].age)
			{
				sorted[k++] = list[i++];
			}
			else
			{
				sorted[k++] = list[j++];
			}
		}
	}

	if (i > mid)
	{
		for (l = j; l <= right; l++)
		{
			sorted[k++] = list[l];
		}
	}
	else
	{
		for (l = i; l <= mid; l++)
		{
			sorted[k++] = list[l];
		}
	}
	for (l = left; l <= right; l++)
	{
		list[l] = sorted[l];
	}
}

void merge_sort(array* list, int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d %s", &name_set[i].age, name_set[i].name);
	}

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

	return 0;
}