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

[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

 

//병합 정렬(Merge Sort)

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

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

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

 

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

int *origin;

int on;

 

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

void MergeSort(int *base, int n);

void ViewArr(int *arr, int n);

int main(void)

{

    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };

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

    origin = arr;

    on = 10;

    ViewArr(origin, on);

    MergeSort(arr, 10);

    ViewArr(origin, on);

    return 0;

}

 

void PrintSpace(int n);

void MergeSort(int *base, int n)

{

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

    int ahalf = n / 2; //배열의 앞쪽 개수

    int bhalf = n - ahalf; //배열의 뒤쪽 개수

    int ai = 0, bi = ahalf;

    int i = 0;

 

    int *tbase = 0;

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

    if (n <= 1)//배열의 크기가 1보다 작거나 같을 때

    {

        return;

    }

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

    MergeSort(base, ahalf);//앞쪽 배열 재귀호출로 정렬

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

    PrintSpace(base - origin);

    ViewArr(base, ahalf);

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

    MergeSort(base + ahalf, bhalf);//뒤쪽 배열 재귀호출로 정렬

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

    PrintSpace(base + ahalf - origin);

    ViewArr(base + ahalf, bhalf);

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

    tbase = (int *)malloc(sizeof(int)*n);//배열 크기의 임시 공간을 할당

    memcpy(tbase, base, sizeof(int)*n);//임시 공간에 배열 메모리 복사

 

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

    while ((ai<ahalf) && (bi<n))

    {

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

        if (tbase[ai] <= tbase[bi])//뒤쪽이 크거나 같을 때

        {

            base[i] = tbase[ai];//앞쪽 배열의 원소를 대입

            ai++;

        }

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

        else

        {

            base[i] = tbase[bi];//뒤쪽 배열의 원소를 대입

            bi++;

        }

        i++;

    }

 

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

    while (ai<ahalf)//앞쪽 배열의 남은 것들을 대입

    {

        base[i] = tbase[ai];

        i++;

        ai++;

    }

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

    while (bi<n)//뒤쪽 배열의 남은 것들을 대입

    {

        base[i] = tbase[bi];

        i++;

        bi++;

    }

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

    free(tbase);//임시 버퍼에 할당한 메모리 해제      

}

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

void PrintSpace(int n)

{

    int i = 0;

    for (i = 0; i<n; i++)

    {

        printf("   ");

    }

}

 

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

void ViewArr(int *arr, int n)

{

    int i = 0;

인덱스 0에서 마지막 요소까지 값을 출력합니다.

    for (i = 0; i<n; i++)

    {

        printf("%2d ", arr[i]);

    }

전체 요소 값을 출력한 후에 개행 문자를 출력합니다.

    printf("\n");

}

[그림 4.1] 병합 정렬