개발/Algorithm

분할정복(Divide and Conquer) - 2. 병합정렬

huiyu 2014. 6. 25. 07:03

병합정렬은 

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이다.


병합정렬 작동 순서

1. 정렬한 데이터 집합을 반으로 나눈다.

2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1을 반복한다.

3. 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단 병합할 때 데이터 집합의 원소는 순서에 맞춰서 정렬한다.

4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다.


5, 1, 6, 4, 8, 3, 7, 9, 2의 데이터를 정렬한다고 할 때 다음의 과정을 거쳐서 정렬을 한다.

먼저 알고리즘의 1-2 과정을 반복해 데이터 집합을 나눈다.

파란색 블록중간의 기준점을 의미



분할을 끝낸 뒤에는 '정복'을 수행, 합칠 때는 데이터를 정렬하며 크기순으로 합치면 된다.




병합정렬알고리즘을 구현하는 MergeSort()함수는 크게 세가지 일을 수행한다.

1. 데이터 집합을 반으로 나누고,

2. 반으로 나눈 데이터 집합을 매개 변수로 삼아 스스로 재귀 호출

3. 둘로 나눈 데이터 집합을 다시 병합



병합을 수행하는 Merge()함수


다음 배열을 실행시켜 보면 병합정렬이 실행됨을 볼 수 있다.




728x90
반응형

'개발 > Algorithm' 카테고리의 다른 글

Quick sort source  (0) 2016.01.17
메모_  (0) 2015.04.08
알고리즘 메모  (0) 2015.03.31
동적 계획법(Dynamic Programming)_1.개념  (0) 2015.03.26
분할정복(Divide and Conquer) - 1. 개념  (0) 2014.06.25