'Divide and Conquer'에 해당되는 글 1건

  1. 2009.03.26 [알고리즘] 합병 정렬 (The divide-and-conquer) (3)

일명 합병 정렬은 merge sort로 잘 알려져 있으며 분할 정복 방식의 정렬 알고리즘이다.

divide: 주어진 문제를 작은 문제로 분할한다.
conquer: 작은 문제를 순환적으로 처리. 즉 더 작은 소문제의 순환이 없을때까지..
merge: 작은 문제에 대한 해를 합병하여 원래 문제에 해를 구한다.

다음 그림은 Introduction to Algorithms에 나와 있는 그림으로써 합병정렬의 모습을
보여 준다.


알고리즘의 Pseudu code는 다음과 같다.

MERGE(A, p, q, r)
n1 q - p + 1
n2 r - q
3  create arrays L[1 n1 + 1] and R[1 n2 + 1]
for i 1 to n1
5       do L[i] A[p + i - 1]
for j 1 to n2
7       do R[j] A[q + j]
L[n1 + 1]
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



오늘 이를 바탕으로 오래간만에 프로그래밍을 해 보았다. 좀 엉성하기는 하지만 그래도 나름대로
잘 돌아가는 것 같다.

저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by sound79 사운드친구

댓글을 달아 주세요

  1. 정신붕괴 2009.03.28 08:53 신고  댓글주소  수정/삭제  댓글쓰기

    작년 알고리즘시간에 봣던 알고리즘인데 갑자기 떠오르네요.ㅎㅎ 잘보고 갑니다.

  2. 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문에서의 조건문을 고쳐야할 것 같은데...
    어떻게 생각하세요??
    제가 아직 배우는 중이라 중요한 부분을 놓쳤을 수도 있습니다~
    가르침 주세요 ㅠㅠㅠㅠㅠ