[디딤돌 자료구조와 알고리즘 with C] 4.3 병합 정렬 알고리즘

4.3 병합 정렬 알고리즘

 이번에는 병합 정렬 알고리즘을 살펴봅시다.

 

 병합 정렬 알고리즘은 배열을 작은 단위의 배열로 분할한 후에 분할한 배열을 정렬하고 이들을 다시 정렬하면서 전체 배열을 정렬하는 알고리즘입니다.

 

병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    ah:= n/2

    bh:= n - ah;

    조건(n이 1보다 작거나 같으면) 종료

    병합정렬(base,ah,compare)

    병합접열(base+ah,bh,compare)

    tbase에 동적 메모리 할당(원소크기*원소개수)

    메모리 복사(tbase,base)

    ai:=0

    bi:=ah

    i:=0

    반복(ai가 ah보다 작으면서 bi가 n보다 작다)

        조건(tbase[ai]가 tbase[bi]보다 작거나 같으면

            base[i] := base[ai]

            ai:= ai+1

        아니면

             base[i]:= base[bi]

             bi:= bi+1

        i:=i+1

    반복(ai가 ah보다 작다)

        base[i]:= tbase[ai]

        i:=i+1

        ai:=ai+1

    반복(bi가 n보다 작다)

        base[i]:= tbase[bi]

        i:=i+1

        bi:=bi+1

 

4.3.1 병합 정렬 알고리즘 성능

병합 정렬 알고리즘 성능을 분석해 보아요.

 

병합 정렬은 배열의 원소가 1개일 때까지 분할하죠.

분할한 두 개의 배열을 하나로 합치기 위해서는 두 배열의 원소 개수만큼 비교해요.

원래 배열을 분할한 배열을 합치기 위해 비교는 n번 수행하겠죠.

결국 분할 횟수 * n 만큼 수행해요.

분할은 원속 개수를 n=>n/2=>n/4... 형태로 분할하므로 2의 h 승이 1이 될 때까지 분할하죠.

수행 속도는 h*n 이예요.

2의 h 승이 n이므로 h는 logn예요.

따라서 수행 속도는 O(nlogn)이라고 말할 수 있어요.

4.3.2 병합 정렬 알고리즘 구현