일명 합병 정렬은 merge sort로 잘 알려져 있으며 분할 정복 방식의 정렬 알고리즘이다.
divide: 주어진 문제를 작은 문제로 분할한다.
conquer: 작은 문제를 순환적으로 처리. 즉 더 작은 소문제의 순환이 없을때까지..
merge: 작은 문제에 대한 해를 합병하여 원래 문제에 해를 구한다.
다음 그림은 Introduction to Algorithms에 나와 있는 그림으로써 합병정렬의 모습을
보여 준다.
알고리즘의 Pseudu code는 다음과 같다.
MERGE(A, p, q, r)
1 n1 ← q - p + 1
2 n2 ← r - q
3 create arrays L[1 ‥ n1 + 1] and R[1 ‥ n2 + 1]
4 for i ← 1 to n1
5 do L[i] ← A[p + i - 1]
6 for j ← 1 to n2
7 do R[j] ← A[q + j]
8 L[n1 + 1] ← ∞
9 R[n2 + 1] ← ∞
10 i ← 1
11 j ← 1
12 for k ← p to r
13 do if L[i] ≤ R[j]
14 then A[k] ← L[i]
15 i ← i + 1
16 else A[k] ← R[j]
17 j ← j + 1
오늘 이를 바탕으로 오래간만에 프로그래밍을 해 보았다. 좀 엉성하기는 하지만 그래도 나름대로
잘 돌아가는 것 같다.
merge_sort.c
'예전글 목록' 카테고리의 다른 글
| 지그비 헬스케어 프로파일 발표 (2) | 2009.03.28 |
|---|---|
| Google 검색의 Wonder wheel 실험 (4) | 2009.03.26 |
| [알고리즘] 합병 정렬 (The divide-and-conquer) (3) | 2009.03.26 |
| Gmail의 송신취소(Undo Send) 기능 사용해 보기 (0) | 2009.03.25 |
| 온라인 세미나: HSPA+에 대한 기술개요와 무선통신 테스트 어플리케이션 향상방안 (0) | 2009.03.24 |
| 스마트 그리드: 원거리에서 생산된 에너지를 어떻게 도시까지? (0) | 2009.03.24 |
댓글을 달아 주세요
정신붕괴 2009.03.28 08:53 신고 댓글주소 수정/삭제 댓글쓰기
작년 알고리즘시간에 봣던 알고리즘인데 갑자기 떠오르네요.ㅎㅎ 잘보고 갑니다.
네. 감사합니다. ^^ 제가 알고리즘에 좀 약해서 정리도 하는겸 해서 앞으로 블로깅할까 생각중입니다. ^^
TheDeepBreath 2011.10.03 22:37 신고 댓글주소 수정/삭제 댓글쓰기
흠...;;; 머지부분에서 문제가좀 있는것 아닌가요;;;
int inputNumberArray[MAX_IN_COUNT]={27,10,12,20,25,13,15,22}; 로 예시잡고
난수를 넣어주는 for문을 주석처리 했는데;;;; 쓰레기값들어가고 난리가나요;;;
디버깅해보니 merge부분에 문제가 있는것 같은데~
LArray[n1] = INFINITY_VALUE; RArray[n2] = INFINITY_VALUE;
이부분이 왜 있는건지 모르겠어요...
그리고 그아래 for문에서의 조건문을 고쳐야할 것 같은데...
어떻게 생각하세요??
제가 아직 배우는 중이라 중요한 부분을 놓쳤을 수도 있습니다~
가르침 주세요 ㅠㅠㅠㅠㅠ