-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmerge.java
150 lines (139 loc) · 5.65 KB
/
merge.java
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
import java.io.*;
public class merge {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int arr[] = new int[Integer.valueOf(br.readLine())];
for(int i=0;i<arr.length;i++){
arr[i] = Integer.valueOf(br.readLine());
}
new merge_sort(arr);
for(int k : arr){
sb.append(String.valueOf(k)+"\n");
}
System.out.print(sb);
}
}
class merge_sort{
//int tmp[];
merge_sort(int arr[]){
int tmp[] = new int[arr.length];
Sort(arr, tmp, 0, arr.length-1);
}
void Sort(int arr[],int tmp[], int start, int end){
if(start<end){
int center = (start+end)/2;
Sort(arr, tmp, start, center);
Sort(arr, tmp, center+1, end);
Merge(arr,tmp,start,center,end);
}
}
void Merge(int arr[],int tmp[],int start,int center, int end){
for(int i = start;i<=end;i++){
tmp[i] = arr[i];
}
int partition1 = start;
int partition2 = center+1;
int idx = start;
while(partition1<=center && partition2<=end){
if(tmp[partition1]<=tmp[partition2]){ //앞쪽 파이티션의 값이 작은 경우
arr[idx] = tmp[partition1];
partition1++;
}
else{ //뒤쪽 파이션의 값이 작은 경우
arr[idx] = tmp[partition2];
partition2++;
}
idx++;
}
for(int i=0;i<=center-partition1;i++){ //앞쪽 파티션에 값이 남아있는 경우 cf.뒤쪽은 그냥 남아있기 때문에 신경 안써도 됨.
arr[idx+i] = tmp[partition1+i];
}
}
}
//2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222
// import java.io.*;
// public class merge{
// static int arr[];
// static int tmp[];
// public static void main(String[] args) throws NumberFormatException, IOException {
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringBuilder sb = new StringBuilder();
// arr = new int[Integer.valueOf(br.readLine())];
// tmp = new int[arr.length];
// for(int i=0;i<arr.length;i++){
// arr[i] = Integer.valueOf(br.readLine());
// }
// merge_sort(0,arr.length-1);
// for(int k : arr){
// sb.append(String.valueOf(k)+"\n");
// }
// System.out.print(sb);
// }
// static void merge_sort(int start, int end){
// if (start < end) {
// int center = (start + end) / 2;
// merge_sort(start, center);
// merge_sort(center + 1, end);
// for(int i = start;i<=end;i++){
// tmp[i] = arr[i];
// }
// int partition1 = start;
// int partition2 = center+1;
// int idx = start;
// while(partition1<=center && partition2<=end){
// if(tmp[partition1]<=tmp[partition2]){ //앞쪽 파이티션의 값이 작은 경우
// arr[idx] = tmp[partition1];
// partition1++;
// }
// else{ //뒤쪽 파이션의 값이 작은 경우
// arr[idx] = tmp[partition2];
// partition2++;
// }
// idx++;
// for(int i=0;i<=center-partition1;i++){ //앞쪽 파티션에 값이 남아있는 경우 cf.뒤쪽은 그냥 남아있기 때문에 신경 안써도 됨.
// arr[idx+i] = tmp[partition1+i];
// }
// }
// }
// }
// }
//11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
// class merge_sort{
// //int tmp[];
// merge_sort(int arr[]){
// int tmp[] = new int[arr.length];
// Sort(arr, tmp, 0, arr.length-1);
// }
// void Sort(int arr[],int tmp[], int start, int end){
// if(start<end){
// int center = (start+end)/2;
// Sort(arr, tmp, start, center);
// Sort(arr, tmp, center+1, end);
// Merge(arr,tmp,start,center,end);
// }
// }
// void Merge(int arr[],int tmp[],int start,int center, int end){
// for(int i = start;i<=end;i++){
// tmp[i] = arr[i];
// }
// int partition1 = start;
// int partition2 = center+1;
// int idx = start;
// while(partition1<=center && partition2<=end){
// if(tmp[partition1]<=tmp[partition2]){ //앞쪽 파이티션의 값이 작은 경우
// arr[idx] = tmp[partition1];
// partition1++;
// }
// else{ //뒤쪽 파이션의 값이 작은 경우
// arr[idx] = tmp[partition2];
// partition2++;
// }
// idx++;
// }
// for(int i=0;i<=center-partition1;i++){ //앞쪽 파티션에 값이 남아있는 경우 cf.뒤쪽은 그냥 남아있기 때문에 신경 안써도 됨.
// arr[idx+i] = tmp[partition1+i];
// }
// }
// }