언어 자료구조 알고리즘/디딤돌 정렬 알고리즘 (C언어)

6. 병합 정렬(Merge Sort) 알고리즘

언제나휴일 2016. 11. 25. 16:30
반응형

6. 병합 정렬(Merge Sort) 알고리즘


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

 

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

 

병합 정렬(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


6.1 병합 정렬 알고리즘 성능 분석

6.2 병합 정렬 알고리즘 구현

6.3 병합 정렬 알고리즘 소스 코드

[C언어] 8가지 정렬 알고리즘

 

 

반응형
1 2 3 4 5 6 7 8 9 ··· 25