이번에는 버블 정렬 알고리즘을 구현하는 예를 보여드릴게요.
먼저 공통으로 사용할 파일을 프로젝트 폴더에 복사한 이후에 프로젝트에 추가하세요. 그리고 헤더 파일을 포함합니다. 이후의 작업에서는 언제나 필요하며 별다른 언급을 하지 않겠습니다.
#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;
}
정상적으로 동작하는지와 정렬할 원소 개수와 수행 속도의 관계가 어떤지 확인해 보세요.