9.4.2 병합 정렬 알고리즘 구현

병합 정렬 알고리즘을 구현합시다.

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

    조건(n<=1) 종료

    h:=n/2

    병합 정렬(base, h, compare)

    병합 정렬(base+h, n- h, compare) 

    ai:=0    bi:=h    ci:=0

    tbase에 크기 n인 버퍼 할당

    반복(ai<h 이면서 bi<n)

        조건(compare(base[ai],base[bi])>0)

            tbase[ci] := base[bi]    bi++

        아니면

            tbase[ci]:= base[ai]    ai++

        ci++

    반복(ai<h)

        tbase[ci]:=base[ai]    ai++, ci++

    반복(bi<n)

        tbase[ci]:=base[bi]    ci++, bi++

    base에 tbase 내용 복사

    tbase 메모리 해제

분할 과정에서 n이 1보다 작거나 같으면 종료합니다.

앞 쪽 요소와 뒤 쪽 요소로 분할합니다.

이제 정복 과정입니다. 정복 과정에 사용할 인덱스를 설정하세요.

임시 버퍼를 할당합니다.

앞 쪽 배열의 요소를 순차 탐색할 ai가 h보다 작으면서 뒤 쪽 배열의 요소를 순차 탐색할 bi가 n보다 작으면 반복합니다.

앞 쪽 요소가 크면 뒤 쪽 요소를 임시 버퍼에 배치하고 bi를 다음 위치로 이동합니다.

그렇지 않으면 앞 쪽 요소를 임시 버퍼에 배치하고 ai를 다음 위치로 이동합니다.

언제나 ci는 다음 위치로 이동합니다.

만약 ai가 h보다 작다면 아직 앞 쪽 요소 중에 임시 버퍼로 배치하지 않은 것들이 있으니 배치하세요.

bi가 n보다 작다면 아직 뒤 쪽 요소 중에 임시 버퍼로 배치하지 않은 것들이 있으니 배치하세요.

마지막으로 임시 버퍼의 내용을 원본 배열에 복사한 후에 임시 버퍼를 소멸하세요.

테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 merge_sort로 변경하세요.

▷ 실행 결과


실습한 결과물은 언제나 휴일 프로그램 소스 사이트에 있습니다.