[알고리즘 C언어] 4.3.2 병합 정렬 알고리즘 구현

이제 병합 정렬 알고리즘을 구체적으로 구현합시다.

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

먼저 두 개의 값을 교환하는 매크로 함수를 작성합니다.

여기에서는 정렬하는 과정을 출력하는 부분이 있습니다. 이를 위해 정렬을 수행하는 배열의 시작 주소와 원소 개수를 기억하는 전역 변수를 선언하세요. 만약 정렬 과정을 출력할 필요가 없다면 주석 처리하세요.

이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요. 원소 형식에 관계없이 정렬하는 방법은 디딤돌 정렬 알고리즘 (C언어)를 참고하세요.

정렬해 나가는 과정을 출력하기 위한 목적으로 배열 주소와 원소 개수를 전역 변수에 설정합니다. 만약 테스트 과정을 출력할 필요가 없다면 주석 처리하세요.

배열을 분할하여 재귀적으로 정렬하는 과정이 필요합니다. 따라서 분할할 앞쪽 배열과 뒤쪽 배열의 원소 개수 및 시작 인덱스를 기억하는 변수를 선언 및 초기화하세요.

재귀의 탈출 조건은 배열의 크기가 1보다 작거나 같을 때입니다.

먼저 앞쪽 배열을 재귀호출로 정렬하세요.

정렬 과정을 보여주기 위해 출력하는 것입니다. 만약 정렬 과정을 보여줄 필요가 없다면 주석 처리하세요.

먼저 앞쪽 배열을 재귀호출로 정렬하세요.

정렬 과정을 보여주기 위해 출력하는 것입니다. 만약 정렬 과정을 보여줄 필요가 없다면 주석 처리하세요.

이제 두 개로 분할하여 각각 정렬한 것을 하나의 배열로 정렬할 것입니다. 이를 위해 원본 배열 크기의 메모리를 동적 할당하고 원본 배열 내용으로 메모리 복사합니다.

앞쪽 배열과 뒤쪽 배열의 마지막 요소를 만나기 전까지 반복합니다.

뒤쪽 배열 요소가 크거나 같을 때는 앞쪽 배열의 원소를 대입합니다.

그렇지 않을 때는 뒤쪽 배열의 원소를 대입합니다.

만약 앞쪽 배열에 남은 것들이 있다면 이들을 모두 대입합니다.

만약 뒤쪽 배열에 남은 것들이 있다면 이들을 모두 대입합니다.

임시로 동적 메모리 할당한 버퍼를 해제합니다.

출력 과정을 표시하기 위해 제공하는 합수입니다. 먼저 재귀 과정에서 자신의 위치 앞쪽을 공백을 출력하기 위한 함수를 작성하세요.

테스트 목적으로 배열의 내용을 출력하는 함수입니다.

병합 정렬 알고리즘
병합 정렬 알고리즘


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.