언어 자료구조 알고리즘/[C]디딤돌 자료구조와 알고리즘

[디딤돌 자료구조와 알고리즘] 4.3.2 병합 정렬 알고리즘 구현

언제나휴일 2016. 4. 10. 15:29
반응형

4.3.2 병합 정렬 알고리즘 구현



병합정렬알고리즘.zip



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


#include "common.h"

#include "Book.h"

typedef void *Element;

typedef int (*Compare)(Element , Element);

 

void merge_sort(Element *base, int n, Compare compare)

{

 n의 절반의 크기를 ahalf에 기억합니다. 이는 배열을 분할할 때 앞쪽 배열의 원소 개수입니다.

    int ahalf = n/2;

 배열을 분할할 때 뒤쪽 배열의 원소 개수를 bhalf에 기억합니다.

    int bhalf = n - ahalf;

 분할할 배열을 하나의 배열로 정복하기 위한 인덱스를 선언합니다. ai는 앞쪽 배열의 인덱스로 사용할 것이므로 0으로 초기화합니다. bi는 뒤쪽 배열의 인덱스로 사용할 것이므로 ahalf로 초기화합니다. 그리고 정렬 상태의 배열을 만들어가는 과정에서의 인덱스로 사용할 i 0으로 초기화합니다.

    int ai=0, bi=ahalf;

    int i=0;

 병합 정렬은 원본 배열의 크기만큼의 메모리를 할당하여 이를 이용하므로 변수를 선언합시다.

    Element *tbase=0;

 

 만약 원소의 개수가 1보다 작거나 같다면 분할할 필요가 없고 정렬할 필요가 없으므로 함수를 종료합니다.

    if(n<=1)

    {

        return;

    }

 

 재귀 호출로 앞쪽 배열을 정렬합니다.

    merge_sort(base, ahalf, compare);

 재귀 호출로 뒤쪽 배열을 정렬합니다.

    merge_sort(base+ahalf, bhalf, compare);

 이제 정렬할 앞쪽 배열과 뒤쪽 배열을 하나의 배열로 정복해야 합니다. tbase에 메모리를 할당하고 원본 배열의 내용을 복사합니다.

    tbase = (Element *)malloc(sizeof(Element)*n);

    memcpy(tbase,base,sizeof(Element)*n);

 

 ai ahalf(앞쪽 배열의 원소 개수)보다 작거나 bi n(배열의 원소 개수)보다 작으면 반복합니다.

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

    {

 복사한 tbase ai인덱스에 있는 원소가 bi인덱스에 있는 원소보다 작거나 같다면 base[i] ai인덱스에 있는 원소를 대입하고 ai 1 증가합니다.

        if(compare(tbase[ai],tbase[bi])<=0)

        {

            base[i] = tbase[ai];

            ai++;

        }

 그렇지 않다면 base[i] bi인덱스에 있는 원소를 대입하고 bi 1 증가합니다.

        else

        {

            base[i] = tbase[bi];

            bi++;

        }

 i 1 증가합니다.

        i++;

    }

 반복문을 빠져 나왔을 때 ai ahalf보다 작다면 bi n에 도달한 것이므로 ai인덱스에서 ahalf 사이에 있는 원소들을 base 배열에 순차적으로 대입합니다.

    while(ai<ahalf)

    {

        base[i] = tbase[ai];

        i++;

        ai++;

    }

 마찬가지로 bi n보다 작다면 ai ahalf에 도달한 것이므로 bi인덱스에서 n사이에 있는 원소들을  base 배열에 순차적으로 대입합니다.

    while(bi<n)

    {

        base[i] = tbase[bi];

        i++;

        bi++;

    }

 임시로 사용한 tbase에 할당한 메모리를 해제합니다.

    free(tbase);

}

 테스트 코드는 다른 정렬 알고리즘과 차이가 없으므로 코드 설명은 생략할게요.

#define MAX_BOOK             4000

Book *books[MAX_BOOK]={0};

void SimulationInit()

{

    char title[MAX_TIT_LEN+1]="";

    char author[MAX_AUT_LEN+1]="";

    int i = 0;

 

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

    {

        sprintf_s(title,sizeof(title),"%010d",rand());

        sprintf_s(author,sizeof(author), "%010d",rand());

        books[i] = New_Book(title,author,rand());

    }

}

 

int CompareByTitle(Book *book1,Book *book2)

{

    return Book_CompareTitle(book1,book2->title);

}

 

int CompareByNum(Book *book1,Book *book2)

{

    return Book_CompareNum(book1,book2->num);

}

 

void ListBook(int n)

{

    int i = 0;

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

    {

        Book_View(books[i]);

    }

}

 

 

 

void Simulation1()

{

    merge_sort((Element *)books,10,CompareByTitle);

    printf("--------제목순-------\n");

    ListBook(10);

    merge_sort((Element *)books,10,CompareByNum);

    printf("--------번호순-------\n");

    ListBook(10);

}

void Simulation2()

{

    clock_t st,et;

    st = clock();

    merge_sort((Element *)books,MAX_BOOK/10,CompareByNum);

    et=clock();

    printf("%d개 정렬에 걸린 시간:%d\n",MAX_BOOK/10,et-st);

    st = clock();

    merge_sort((Element *)books,MAX_BOOK,CompareByNum);

    et=clock();

    printf("%d개 정렬에 걸린 시간:%d\n",MAX_BOOK,et-st);

}

void SimulationClear()

{

    int i = 0;

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

    {

        Delete_Book(books[i]);

    }

}

int main()

{

    SimulationInit();

    Simulation1();

    Simulation2();

    SimulationClear();

    return 0;

}

 

▷실행 결과

--------제목순-------

<0000006334>:<0000000041>

              저자:0000018467

<0000017421>:<0000000292>

              저자:0000012382

<0000011942>:<0000000491>

              저자:0000002995

<0000032391>:<0000004827>

              저자:0000005436

<0000026962>:<0000011478>

              저자:0000029358

<0000000153>:<0000014604>

              저자:0000003902

<0000019895>:<0000018716>

              저자:0000019718

<0000009961>:<0000023281>

              저자:0000016827

<0000028145>:<0000024464>

              저자:0000005705

<0000015724>:<0000026500>

              저자:0000019169

--------번호순-------

<0000000153>:<0000014604>

              저자:0000003902

<0000006334>:<0000000041>

              저자:0000018467

<0000009961>:<0000023281>

              저자:0000016827

<0000011942>:<0000000491>

              저자:0000002995

<0000015724>:<0000026500>

              저자:0000019169

<0000017421>:<0000000292>

              저자:0000012382

<0000019895>:<0000018716>

              저자:0000019718

<0000026962>:<0000011478>

              저자:0000029358

<0000028145>:<0000024464>

              저자:0000005705

<0000032391>:<0000004827>

              저자:0000005436

400개 정렬에 걸린 시간:0

4000개 정렬에 걸린 시간:4


4.3 병합 정렬 알고리즘

반응형