2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬
📎 병합 정렬 Merge sort
병합 정렬은 정렬을 앞부분과 뒷부분으로 나눈 후 정렬하고, 병합하는 과정을 반복하는 정렬이다.
성능은 퀵정렬보다 떨어지는 편이고 메모리도 많이 쓰지만 안정형 정렬이라는 장점을 가지고 있다.
먼저 이 배열을 앞부분과 뒷부분으로 나눠준다.
그리고 또 앞부분과 뒷부분을 나눠줬다.
여기서 더 이상 나눠지지 않으니 정렬을 시작한다.
앞부분에서 정렬, 뒷부분에서 정렬해준다.
그리고 앞부분 모두를 다시 정렬한다.
뒷부분도 위와 같은 과정을 반복한다.
앞부분과 뒷부분이 잘 정렬이 되었다.
이제 이 두 부분을 가지고 비교, 합병을 한다.
두 부분에서 가장 작은 값끼리 비교를 한다.
0이 작으니 0의 위치는 정해졌고
0을 뺀 앞부분에서 가장 작은 값과 뒷부분 작은 값끼리 비교한다.
이 과정을 계속 반복한다.
잘 정렬이 됐다.
병합 정렬의 순서
- 배열을 반절 나눠 앞부분 그룹과 뒷부분 그룹으로 나눔
- 배열의 앞 그룹 병합 정렬
- 배열의 뒷 그룹 병합 정렬
- 정렬된 앞그룹, 뒷그룹 요소 순서대로 하나씩 비교
- 정렬된 배열 저장
병합 정렬 과정을 자바로 구현하면 이렇다.
|
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
|
import java.util.Scanner;
public class MergeSort {
/*
* 병합 정렬 : 정렬을 앞그룹, 뒷그룹으로 나눠 정렬하고 병합하는 정렬
* 분할 정복법 (Divide and Conquer)
* 일반적인 병합 정렬의 시간 복잡도는 O(n log n)
*
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정렬할 요소의 수: ");
int n = sc.nextInt();
int[] arr = new int[n];
//요소 입력받음
for(int i=0; i<n; i++) {
arr[i]=sc.nextInt();
}
sc.close();
mergeSort(arr, n);
System.out.println("병합 정렬 완료");
//정렬 후 출력
for(int i=0; i<n; i++) {
System.out.print(arr[i]+" ");
}
}
//병합 정렬
static void mergeSort(int[] arr, int n) {
int[] tmp = new int[n]; //작업용 임시 저장공간
underMergeSort(arr, tmp, 0, n-1);
tmp = null;
}
//재귀적으로 병합 정렬
static void underMergeSort(int[] arr, int[] tmp, int first, int last) {
if(first<last) { //첫번째 요소가 마지막 요소보다 작을때 동안 반복
int center = (first + last)/2;
underMergeSort(arr, tmp, first, center); //앞 그룹을 병합 정렬함
underMergeSort(arr, tmp, center+1, last); //뒷 그룹을 병합 정렬함
merge(arr, tmp, first, center, last); //병합
}
}
static void merge(int[] arr, int[] tmp, int first, int center, int last) {
//작업용 tmp 배열에 복사해옴
for(int i=first; i<=last; i++) {
tmp[i]=arr[i];
}
int pointF = first; //앞그룹의 첫요소
int pointL = center+1; //뒷그룹의 첫요소
int idx = first; //새로 넣을 배열 인덱스
//두 그룹 정렬 진행(진행방향은 ->)
while(pointF <= center && pointL <= last) {
//요소끼리 비교
//앞그룹 요소가 작으면
if(tmp[pointF] <= tmp[pointL]) {
arr[idx] = tmp[pointF]; //앞그룹 요소로 저장
pointF++;
} else {
arr[idx] = tmp[pointL]; //뒷그룹 요소로 저장
pointL++;
}
idx++;
}
//앞 그룹의 요소가 남아있을 경우 (tmp에 앞 그룹 요소가 아직 다 안들어간 경우)
for(int i=0; i<=center-pointF; i++) {
arr[idx + i] = tmp[pointF + i];
}
}
}
|
cs |
병합 정렬의 성능 분석
정렬할 요소가 n개 일때 병합 정렬은 log n의 단계가 필요하다.
그래서 병합 정렬의 시간 복잡도는 O(n log n)이다.
항상 반절로 나눠 두 부분끼리 비교 정렬되기 때문에 평균적으로 O(n log n)이 유지가 된다.
+참고
https://www.youtube.com/watch?v=XaqR3G_NVoo
+
[자료구조 알고리즘] 병합정렬(Merge Sort) 구현하기
youtu.be
'자료구조 & 알고리즘' 카테고리의 다른 글
| [정렬 알고리즘] 힙 정렬 (0) | 2021.10.01 |
|---|---|
| [알고리즘] 다이나믹 프로그래밍 (동적 계획법) (1) | 2021.09.09 |
| [정렬 알고리즘] 삽입 정렬 (0) | 2021.09.08 |
| [정렬 알고리즘] 버블 정렬 (0) | 2021.09.08 |
| [정렬 알고리즘] 선택 정렬 (0) | 2021.09.07 |
댓글