[C언어 소스] 병합 정렬(Merge Sort, 합병 정렬) 알고리즘

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

 

병합정렬

 

병합 정렬(Merge Sort).c

 

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

 

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;

 

    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;

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

    {

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

    }

    printf("\n");

}

 

자세히 보기

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

병합 정렬 알고리즘 구현

C++ 병합 정렬 알고리즘