본문 바로가기
[C++] 알고리즘 교육/15. 분할정복법

[알고리즘 15.1.2] 분할정복법 - 합병정렬구현하기

by 안산학생 2019. 4. 24.

문제


서로 다른 n개의 정수가 주어질 때, 이를 합병정렬을 이용하여 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력


첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다.  

출력


첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10 2 5 3 4 8 7 -1 9 10 2

예제 출력

-1 2 2 3 4 5 7 8 9 10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
 
void merging(int arr[], int s1, int e1, int s2, int e2);
void mergeSort(int arr[], int start, int end){
  
  if(start>=end){
    return;
  }else{
    
    int mid = (start+end)/2;
    
    mergeSort(arr, start, mid);
    mergeSort(arr, mid+1end);
    
    merging(arr, start, mid, mid+1end);
    
  }
  
}
 
void merging(int arr[], int s1, int e1, int s2, int e2){
  
  int p = s1;
  int q = s2;
  int temp[100005];
  int temp_idx=0;
  
  while(p<=e1 && q<= e2){
    
    if(arr[p]<=arr[q]){
      temp[temp_idx++= arr[p];
      p++;
    }else{
      temp[temp_idx++= arr[q];
      q++;
    }
    
  }
  
  if(p>e1){
    for(int i=q; i<=e2; i++){
      temp[temp_idx++= arr[i];
    }
  }else{
    for(int i=p; i<=e1; i++){
      temp[temp_idx++= arr[i];
    }
  }
  
  for(int i=s1; i<=e2; i++){
    arr[i] = temp[i-s1];
  }
  
}
 
int main() {
  
  int n;
  int numbers[100005];
  
  scanf("%d",&n);
  
  for(int i=0; i<n; i++scanf("%d",&numbers[i]);
  
  mergeSort(numbers, 0, n-1);
  
  for(int i=0; i<n; i++printf("%d ",numbers[i]);
  
  return 0;
}
 

댓글