옛날../미분류
[자바] 합병정렬 자바 코드
도로롱주
2017. 11. 21. 16:14
합병 정렬
시간복잡도가 낮은 정렬 방법입니다.
합병정렬: O(nLog n)
아래 그림처럼 최소단위로 분할한뒤 다시 합치는데
합치는 과정에서 정렬을 하게 됩니다.
반복되는 합병 과정에서 정렬된 배열 간 합병만 발생하기 때문에 시간복잡도가 낮습니다.
합병 정렬 자바 코드입니다.
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
|
//합병정렬
public void mergeSort(int[] arr) {
if(arr.length > 1) {
int[] left = new int[arr.length/2];
int[] right = new int[arr.length - left.length];
for(int i=0;i<left.length;i++)
left[i] = arr[i];
for(int i=0;i<right.length;i++)
right[i] = arr[i+left.length];
mergeSort(left);
mergeSort(right);
merge(left, right, arr);
}else {
return ;
}
}
//합병
public void merge(int[] left, int[] right, int[] arr) {
int leftIdx = 0;
int rightIdx = 0;
int arrIdx = 0;
while (leftIdx < left.length) {
if (rightIdx < right.length) {
if ( left[leftIdx] < right[rightIdx]) {
arr[arrIdx] = left[leftIdx];
leftIdx++;
}else{
arr[arrIdx] = right[rightIdx];
rightIdx++;
}
arrIdx++;
}else {
while (leftIdx < left.length) {
arr[arrIdx] = left[leftIdx];
leftIdx++;
arrIdx++;
}
}
}
while (rightIdx < right.length) {
arr[arrIdx] = right[rightIdx];
rightIdx++;
arrIdx++;
}
}
|
cs |
위 코드에서
1
|
mergeSort(arr);
|
cs |
를 호출하면 인자로 넘긴 배열이 오름차순 정렬됩니다.
※다른 얘기지만 자바에서는 기본 자료형을 제외하고 전부 Call By Reference 방식이기 때문에 return 없이 처리 가능합니다.