반응형
Merge sort(병합 정렬)는 원소들 간의 비교를 통해 정렬하는 비교 기반 정렬 알고리즘이다.
원소들 중 같은 값이 있는 경우 정렬 후에도 순서가 유지된다.
정렬의 과정은 분할 -> 정복 -> 합병(결합) 의 순서로 이루어진다.
합병 정렬은 다음과 같이 작동한다.
- 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
- 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
- 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
시간 복잡도는 N 개의 데이터를 정렬할 때를 기준으로 O(N * logN)이다.
Merge sort의 정렬과정을 예를 들면 아래와 같다.
처음에 초기배열 상태에서 가운데를 기준으로 반으로 나누어 분할 상태가 된다.
이후 분할된 앞쪽과 뒷쪽을 각각 정렬(정복이라 칭함) 수행 후 다시 하나의 배열로 만드는 결합 과정을 수행하는 방식이다.
아래는 위키피디아에 나온 병합 정렬 과정의 수행 절차를 나타낸 것이다.
반응형
'프로그래밍' 카테고리의 다른 글
| strcmp(), strtok() (0) | 2020.10.08 |
|---|---|
| 삽입정렬 (Insertion Sort) (0) | 2020.08.21 |
| 구글은 소프트웨어를 어떻게 테스트하는가? (0) | 2020.05.26 |
| [C++] 디폴트 매개변수, default parameter (0) | 2019.08.14 |
| bind error 방지 (0) | 2010.07.17 |
