자료구조와 알고리즘 - 언제나 휴일

이번에는 버블 정렬 알고리즘을 구현하는 예를 보여드릴게요.

먼저 공통으로 사용할 파일을 프로젝트 폴더에 복사한 이후에 프로젝트에 추가하세요. 그리고 헤더 파일을 포함합니다. 이후의 작업에서는 언제나 필요하며 별다른 언급을 하지 않겠습니다.

#include "Book.h"

여기에서 정의할 버블 정렬은 원소 형식에 관계없이 동적으로 생성한 개체의 집합을 정렬하게 정의할 것입니다. 이를 위해 void * 형식을 Element 형식 이름으로 정의할게요.

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

버블 정렬은 n개의 원소가 있는 배열의 주소와 원소 개수 및 비교 알고리즘을 입력 인자로 필요합니다.

void bubble_sort(Element *base, int n, Compare compare)
{

외부 반복문에서는 정렬할 원소의 개수를 줄여나가면서 작업을 수행하고 내부 반복문에서는 앞에서부터 순차적으로 이동하면서 정렬합니다. 이를 위해 두 개의 변수를 선언합시다.

    int i = 0;
    int j = 0;

외부 반복문은 정렬할 범위를 점진적으로 줄여 나갑니다.

    for(i=n; i>1; i--)

    {

내부 반복문은 앞에서부터 순차적으로 이동합니다. 비교할 때 앞에 원소와 비교할 것이므로 j를 1로 초기화하고 있습니다.

        for(j=1; j<i; j++)
        {

j번째 원소와 앞의 원소를 비교하여 앞의 원소가 크면 교환합니다.

            if(compare(base[j-1],base[j])>0)
            {
                Element temp = base[j-1];
                base[j-1] = base[j];
                base[j]=temp;
            }
        }
    }
}

위 알고리즘이 제대로 작성한 것인지와 수행 속도를 확인해 봅시다.

먼저 시뮬레이션에서 사용할 배열을 선언합니다.

#define MAX_BOOK    10000
Book *books[MAX_BOOK]={0};

시뮬레이션을 하기 위해 필요한 초기 작업을 수행하는 함수를 작성합시다.

void SimulationInit()
{

시뮬레이션을 초기화하는 함수에서는 도서 개체를 생성하는 작업을 할 것입니다. 도서 제목과 저자명을 입력받기 위한 변수와 여러 개의 도서 개체를 만들기 위해 Loop 수행 횟수를 기억할 변수를 선언합니다.

    char title[MAX_TIT_LEN+1]="";
    char author[MAX_AUT_LEN+1]="";
    int i = 0;

순차적으로 수행할 것입니다.

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

도서 제목과 저자명을 랜덤한 문자열로 만들게요. 편의상 sprintf를 이용하여 정수문자 형태의 문자열을 만들게요.

        sprintf(title,"%010d",rand());
        sprintf(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()
{

bubble_sort 함수를 호출하여 도서 제목 순으로 정렬합시다. 이를 위해 세번째 인자로 CompareByTitle을 전달합니다. 여기에서는 정렬을 제대로 수행하는지 확인하기 위한 목적이므로 10개의 원소만 정렬할게요.

    bubble_sort(books,10,CompareByTitle);
    printf("--------제목순-------\n");
    ListBook(10);

bubble_sort 함수를 호출하여 번호 순으로 정렬합시다.

    bubble_sort(books,10,CompareByNum);
    printf("--------번호순-------\n");
    ListBook(10);
}

수행 속도를 확인하기 위한 시뮬레이션 함수도 작성합시다.

void Simulation2()
{

속도를 확인하기 위해 clock_t 변수를 두 개 선언합니다. 하나는 정렬을 수행하기 전의 시간을 기억하기 위한 변수이고 하나는 수행한 후의 시간을 기억하기 위한 변수입니다. 참고로 clock_t 형식은 시스템에서 자원 사용에 관한 회계를 위해 정의한 논리적 시간으로 운영체제에 따라 단위가 다릅니다. 여기에서는 상대적인 시간을 비교하기 위함이므로 단위가 얼마인지는 중요하지 않습니다.

    clock_t st,et;

bubble 정렬 알고리즘을 수행하기 전에 시간을 측정합니다.

    st = clock();

bubble 정렬 알고리즘을 수행합니다. 비교를 위해 MAX_BOOK/10개의 원소를 정렬할게요.

    bubble_sort(books,MAX_BOOK/10,CompareByTitle);

다시 시간을 측정하여 얼마의 시간이 걸렸는지 출력합니다.

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

같은 방법으로 MAX_BOOK개수를 정렬하여 시간을 측정하고 출력합니다. 버블 정렬은 수행 속도가 O(n^2)이고 정렬할 원소 개수를 10배 늘렸으므로 약 100배의 시간이 들 것입니다.

    st = clock();
    bubble_sort(books,MAX_BOOK,CompareByTitle);
    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]);
    }
}

이제 진입점인 main 함수를 구현합시다.

int main()
{
    SimulationInit();
    Simulation1(); //제대로 동작하는지 확인
    Simulation2(); //수행 속도 확인
    SimulationClear();
    return 0;
}

정상적으로 동작하는지와 정렬할 원소 개수와 수행 속도의 관계가 어떤지 확인해 보세요.

[카테고리:] <span>자료구조와 알고리즘</span>

2.3.2 버블 정렬 구현