Baekjoon[C언어] - 2751번 수 정렬하기 2(병합 정렬)

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

2751번: 수 정렬하기 2

---

문제

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

---

풀이

배열 병합의 시간 복잡도는 O(n)이다. 데이터 원소 수가 n일 때, 병합 정렬의 단계가 log n 만큼 필요하다.

그러므로 전체 시간 복잡도는 O(n log n)이기 때문에 병합 정렬 알고리즘을 사용하여 

위 조언을 따르도록 하겠다.

 

22.03.01. 작성 중

책 p277

 

 

전체 코드이다.

#include<stdio.h>
#include<malloc.h>

// 수 정렬하기 2

// 병합정렬 사용함

void merge(int* arr, int p, int q, int end);

void mergeSort(int* arr, int start, int end);

int main() {
  int N;

  scanf("%d", &N);

  int* arr = (int*)malloc(sizeof(int) * N);

  for (int i = 0; i < N; i++)
    scanf("%d", &arr[i]);

  mergeSort(arr, 0, N - 1);

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

  free(arr);

  return 0;
}

void merge(int* arr, int p, int q, int r) {
  int pa = p;
  int pb = q + 1;
  int pc = 0;
  int* forWork = (int*)malloc(sizeof(int) * (r - p + 1));

  while (pa <= q && pb <= r) {
    if (arr[pa] <= arr[pb])
      forWork[pc++] = arr[pa++];
    else
      forWork[pc++] = arr[pb++];
  }

  while (pa <= q)
    forWork[pc++] = arr[pa++];

  while (pb <= r)
    forWork[pc++] = arr[pb++];

  pc = 0;
  while (p <= r)
    arr[p++] = forWork[pc++];

  free(forWork);
}

void mergeSort(int* arr, int start, int end) {
  int center;

  if (start < end) {
    center = (start + end) / 2;
    mergeSort(arr, start, center);
    mergeSort(arr, center + 1, end);
    merge(arr, start, center, end);
  }
}

 

 

---

참고자료

 

Do it! 자료구조와 함께 배우는 알고리즘 입문(파이썬 편)