일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 프로그래밍
- 파이썬
- python
- 라즈베리파이3
- 철학
- 자작시
- 파이썬 강의
- 라즈베리파이 모니터
- 라즈베리파이
- 다이나믹프로그래밍
- 계획
- 백준
- 2021
- 머신러닝
- dynamic programming
- 강좌
- C++
- 슬픔
- mmcv
- 파이썬 강좌
- 알고리즘
- mmdetection
- 2020
- python 강좌
- it
- python 강의
- BOJ
- 강의
- dp
- 공부
- Today
- Total
Stargazer
[알고리즘] Mergesort (합병 정렬) 이론 간략 정리 본문
단순 합병 문제:
두 시퀀스 A, B를 오름차순으로 주어진다고 할때, 두 시퀀스를 하나로 합병한, 정렬된 시퀀스 C를 구하라(C 크기 = n)
합병 전략:
A,B의 최소값 중 더 작은값을 C에 넣는데, 만약 최소값이 A 에 있다고 가정하면,
A의 최소값을 C에 넣고, A의 나머지와 B, 그리고 C 를 재귀적으로 함수를 호출하여
합병을 한다.(분할 정복)
합병 수도코드:
Merge(A,B,C)
if(A is empty)
rest of C = rest of B
else if(B is empty)
rest of C = rest of A
else if (first of A <= first of B)
first of C = first of A
merge(rest of A, B, rest of C)
else
first of C = first of B
merge(A, rest of B, rest of C)
return
비어있다면 남은 시퀀스의 나머지 모두 C 뒤에 넣고,
아니라면, 둘이 비교하여 작은값을 넣고,
나머지들은 재귀함수의 인자로 넣어서 처리한다.
Worst-case : 둘이 번갈아가면서 비교하는 경우 가장 많은 비교연산을 수행한다. 이때, n개가 있고, 마지막 요소는 비교를 하지 않고 C의 마지막에 넣으면 되므로, n-1번 수행한다.
$\therefore W(n) = n - 1$
합병정렬 알고리즘:
정렬되지 않는 시퀀스 둘을 정렬된 시퀀스로 합병할때 사용한다.
시퀀스를 둘로 나누어서 각 시퀀스를 정렬한 후에 두 시퀀스를 합병하는 방식으로 분할정복 알고리즘을 이용하자.
요소가 1개면 정렬된거라 가정하고 합병을 수행한다.(위 수도코드 참조)
void mergeSort(Element[] E, int first, int last){
if(first < last){
int mid = (first + last) / 2; // middle index
mergeSort(E, first, mid); //L Sorting(Divide)
mergeSort(E, mid+1, last); //G Sorting(Divide)
merge(E, first, mid, last); // Conquer & Combine
}
return;
}
mergesort 과정은 이진트리 형태로 볼 수 있는데,
각 depth 별로 수행하는 연산은 $O(n)$으로 수행하게 되고,
height가 k라고 하면, 가장 아래로 내려갔을때 요소는 1이고, 이진트리이기때문에 depth 당 1/2씩 크기가 줄기때문에
$n(\frac{1}{2})^k = 1 , n = 2^k$이라 볼 수 있다.
따라서 $k = log_2n$ 이므로
height는 $O(logn)$이라 볼 수 있기 때문에,
해당 알고리즘의 Worst case의 시간복잡도는 아래식으로 나타낼 수 있다.
$W(n) = W(n/2) + W(n/2) + W_{merge}(n) \in \theta (n\log n)$ <- height* (depth 별 연산 수) = $O(n\log n)$
$W_{merge}(n) = n-1 $ <- 위 수도코드 참조
$W(1) = 0$ <- 요소가 1개면 이미 정렬되었다고 가정
'Undergraudate basics(학부생 기초) > 자료구조, 알고리즘' 카테고리의 다른 글
[백준] 12865번: 평범한 배낭 C++ (0) | 2022.05.11 |
---|---|
[백준] 13549번 : 숨바꼭질 3 C++ 풀이 (0) | 2022.05.10 |
[알고리즘] Inplace-Quick sort 이론 간략 정리 (0) | 2022.03.30 |
[알고리즘] Quick sort(퀵소트) 이론 정리 (0) | 2022.03.29 |
[자료구조] 트리 후위순회 결과와 깊이 순서로 트리 구조 구하기 (0) | 2021.04.23 |