이번에는 순차 정렬 알고리즘을 구현해 보기로 해요.
순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
반복(j:=i+1->n)
조건(compare(base[i], base[j]) > 0)
교환(base[i],base[j])
이번에는 순차 정렬 알고리즘을 구현하는 예를 보여드릴게요.
먼저 공통으로 사용할 파일을 프로젝트 폴더에 복사한 이후에 프로젝트에 추가하세요. 그리고 헤더 파일을 포함합니다. 이후의 작업에서는 언제나 필요하며 별다른 언급을 하지 않겠습니다.
#include "Book.h"
여기에서 정의할 버블 정렬은 원소 형식에 관계없이 동적으로 생성한 개체의 집합을 정렬하게 정의할 것입니다. 이를 위해 void * 형식을 Element 형식 이름으로 정의할게요.
typedef void *Element; typedef int (*Compare)(Element , Element);
매크로 함수로 Element 형식을 교환하는 swap 메서드를 정의합시다.
#define swap(x,y) {Element temp =x; x=y; y=temp;}
순차 정렬은 n개의 원소가 있는 배열의 주소와 원소 개수 및 비교 알고리즘을 입력 인자로 필요합니다.
외부 반복문에서는 루프 인덱스 변수 i를 0에서 순차적으로 증가시키며 내부 반복문을 수행합니다.
내부 반복문에서는 i의 다음 위치부터 순차적으로 다음 요소들의 인데스로 증가하며 비교 작업을 반복합니다.
만약 인덱스 i의 요소가 인덱스 j의 요소보다 크면 둘의 위치를 교환합니다.
void sequential_sort(Element *base, int n, Compare compare)
{
int i, j;
//외부 반복문에서는 루프 인덱스 변수 i를 0에서 순차적으로 증가시키며 내부 반복문을 수행합니다.
for(i = 0; i<n; i++) //반복(i:=0->n)
{
//내부 반복문에서는 i의 다음 위치부터 순차적으로 다음 요소들의 인데스로 증가하며 비교 작업을 반복합니다.
for( j=i+1; j<n; j++)//반복(j:=i+1->n)
{
//만약 인덱스 i의 요소가 인덱스 j의 요소보다 크면 둘의 위치를 교환합니다.
if(compare(base[i],base[j])>0)//조건(compare(base[i], base[j]) > 0)
{
swap(base[i],base[j]); //교환(base[i],base[j])
}
}
}
}
위 알고리즘이 제대로 작성한 것인지와 수행 속도를 확인해 봅시다.
먼저 시뮬레이션에서 사용할 배열을 선언합니다.
#define MAX_BOOK 10000
Book *books[MAX_BOOK]={0};
시뮬레이션을 하기 위해 필요한 초기 작업을 수행하는 함수를 작성합시다.
시뮬레이션을 초기화하는 함수에서는 도서 개체를 생성하는 작업을 할 것입니다. 도서 제목과 저자명을 입력받기 위한 변수와 여러 개의 도서 개체를 만들기 위해 Loop 수행 횟수를 기억할 변수를 선언합니다.
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를 이용하여 정수문자 형태의 문자열을 만들게요.
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()
{
// sequential_sort 함수를 호출하여 도서 제목 순으로 정렬합시다. 이를 위해 세번째 인자로 CompareByTitle을 전달합니다. 여기에서는 정렬을 제대로 수행하는지 확인하기 위한 목적이므로 10개의 원소만 정렬할게요.
sequential_sort(books,10,CompareByTitle);
printf("--------제목순-------\n");
ListBook(10);
// sequential_sort 함수를 호출하여 번호 순으로 정렬합시다.
sequential_sort(books,10,CompareByNum);
printf("--------번호순-------\n");
ListBook(10);
}
수행 속도를 확인하기 위한 시뮬레이션 함수도 작성합시다. 속도를 확인하기 위해 clock_t 변수를 두 개 선언합니다. 하나는 정렬을 수행하기 전의 시간을 기억하기 위한 변수이고 하나는 수행한 후의 시간을 기억하기 위한 변수입니다. 참고로 clock_t 형식은 시스템에서 자원 사용에 관한 회계를 위해 정의한 논리적 시간으로 운영체제에 따라 단위가 다릅니다. 여기에서는 상대적인 시간을 비교하기 위함이므로 단위가 얼마인지는 중요하지 않습니다.
void Simulation2()
{
clock_t st,et;
// sequential 정렬 알고리즘을 수행하기 전에 시간을 측정합니다.
st = clock();
// sequential 정렬 알고리즘을 수행합니다. 비교를 위해 MAX_BOOK/10개의 원소를 정렬할게요.
sequential _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();
sequential_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;
}
정상적으로 동작하는지와 정렬할 원소 개수와 수행 속도의 관계가 어떤지 확인해 보세요.
다음은 테스트에 사용한 전체 코드입니다.
#include "Book.h"
typedef void *Element;
typedef int (*Compare)(Element , Element);
#define swap(x,y) {Element temp =x; x=y; y=temp;}
void sequential_sort(Element *base, int n, Compare compare)//버블 정렬(base:배열의 시작 주소, n: 원소 개
, compare:비교 논리)
{
int i, j;
for(i = 0; i<n; i++) //반복(i:=0->n)
{
for( j=i+1; j<n; j++)//반복(j:=i+1->n)
{
if(compare(base[i],base[j])>0)//조건(compare(base[i], base[j]) > 0)
{
swap(base[i],base[j]); //교환(base[i],base[j])
}
}
}
}
#define MAX_BOOK 10000
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()
{
sequential_sort(books,10,CompareByTitle);
printf("--------제목순-------\n");
ListBook(10);
sequential_sort(books,10,CompareByNum);
printf("--------번호순-------\n");
ListBook(10);
}
void Simulation2()
{
clock_t st,et;
st = clock();
sequential_sort(books,MAX_BOOK/10,CompareByTitle);
et=clock();
printf("%d개 정렬에 걸린 시간:%d\n",MAX_BOOK/10,et-st);
st = clock();
sequential_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]);
}
}
int main()
{
SimulationInit();
Simulation1();
Simulation2();
SimulationClear();
return 0;
}
이를 수행하였을 때 나온 결과예요. 물론 수행하는 컴퓨터에 따라 결과는 조금씩 다를 수 있어요.
▷수행 결과
정렬 전
0000757147,이름0167851000
0301413356,이름0336971124
0659598368,이름0160567225
0391749387,이름0004890851
0035766290,이름0026239572
0473038164,이름0000597006
0003615544,이름0326051436
0392289610,이름0118341522
0170427798,이름0037215528
0675016433,이름0168544290
번호로 정렬 후
0000757147,이름0167851000
0003615544,이름0326051436
0035766290,이름0026239572
0170427798,이름0037215528
0301413356,이름0336971124
0391749387,이름0004890851
0392289610,이름0118341522
0473038164,이름0000597006
0659598368,이름0160567225
0675016433,이름0168544290
이름으로 정렬 후
0473038164,이름0000597006
0391749387,이름0004890851
0035766290,이름0026239572
0170427798,이름0037215528
0392289610,이름0118341522
0659598368,이름0160567225
0000757147,이름0167851000
0675016433,이름0168544290
0003615544,이름0326051436
0301413356,이름0336971124
수행 성능 테스트1 자료 개수:1000
수행 속도:4985
수행 성능 테스트2 자료 개수:100
수행 속도:50
수행 결과를 보면 번호 순과 이름 순으로 정렬하는 것을 알 수 있습니다.
그리고 수행 성능을 테스트 한 것을 보면 자료의 개수를 MAX_DATA로 할 때가 MAX_DATA/10으로 할 때보다 100배 가까이 느린 것을 알 수 있습니다.
순차 정렬 알고리즘을 분석하였을 때 계산한 O(n^2)와 결과가 비슷한 것을 알 수 있습니다.
알고리즘 성능을 분석할 때 수학적으로 계산해서 증명할 수 있으면 좋겠죠. 만약 그렇지 못한다면 지금처럼 실제 수행 시간을 측정하여 비교해 보세요.