C언어 228제] NCP Lv3 수 정렬하기 2

출처 : 반크_반크 20년 백서

 

문제]

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 
5
5
4
3
2
1

예제 출력 1 
1
2
3
4
5

 

출처 : 백준_2751번

 

 

참고풀이]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int M[1000000];
int B[1000000];

void merge(int A[], int low, int mid, int hight)
{
   int i, j, k;
   i = low; j = mid + 1; k = 0;

   while (i <= mid && j <= hight)
   {
      if (A[i] <= A[j]) B[k++] = A[i++];
      else B[k++] = A[j++];
   }
   while (i <= mid) B[k++] = A[i++];
   while (j <= hight) B[k++] = A[j++];
   k--;
   while (k >= 0)
   {
      A[low + k] = B[k];
      k--;
   }
}

void MergeSort(int A[], int low, int hight)
{
   int mid;
   if (low < hight)
   {
      mid = (low + hight) / 2;
      MergeSort(A, low, mid);
      MergeSort(A, mid + 1, hight);
      merge(A, low, mid, hight);
   }
}

int main()
{
   int N;
   int i, j;

   scanf("%d", &N);
   if (N >= 1 && N <= 1000000)
   {
      for (i = 0;i < N;i++)
         scanf("%d", &M[i]);

      MergeSort(M, 0, N - 1);

      for (i = 0;i < N;i++)
         printf("%d\n", M[i]);
   }

   return 0;
}

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도