9월 11일(일) - 정렬(2751번)

정렬 - 2751번

2751번: 수 정렬하기 2

 

문제점

1. n의 범위가 1,000,000까지라는 점을 놓치고 리스트의 범위를 설정해서 시간초과 및 런타임에러가 발생했었다

-> list 와 sorted의 범위를 1,000,000까지로 설정

 

 

풀이

(합병 정렬을 이용한 풀이)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>
int list[1000000] = { 0, };
int sorted[1000000] = { 0, };

void merge(int 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] <= list[j])
		{
			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(int 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 i;
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &list[i]);
	}

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

	return 0;
}