1.3 순차 정렬 알고리즘 소스
다음은 테스트에 사용한 전체 코드입니다.
//Book.h
#pragma once
#define MAX_TIT_LEN 200
#define MAX_AUT_LEN 20
typedef struct _Book Book;
struct _Book
{
char title[MAX_TIT_LEN+1];
char author[MAX_AUT_LEN+1];
int num;
};
Book *New_Book(const char *title,const char *author,int num);
void Delete_Book(Book *book);
void Book_View(Book *book);
int Book_CompareTitle(Book *book,const char *title);
int Book_CompareAuthor(Book *book,const char *author);
int Book_CompareNum(Book *book,int num);
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
//Book.c
#include "Book.h"
void Book_Book(Book *book,const char *title,const char *author,int num);
Book *New_Book(const char *title,const char *author,int num)
{
Book *book = 0;
book = (Book *)malloc(sizeof(Book));
Book_Book(book,title,author,num);
return book;
}
void Book_Book(Book *book,const char *title,const char *author,int num)
{
memset(book,0,sizeof(Book));
strncpy_s(book->title,MAX_TIT_LEN,title,MAX_TIT_LEN);
strncpy_s(book->author,MAX_AUT_LEN,author,MAX_AUT_LEN);
book->num = num;
}
void Delete_Book(Book *book)
{
free(book);
}
void Book_View(Book *book)
{
printf("<%010d>:<%s>\n",book->num,book->title);
printf("\t 저자:%s\n",book->author);
}
int Book_CompareTitle(Book *book,const char *title)
{
return strcmp(book->title,title);
}
int Book_CompareAuthor(Book *book,const char *author)
{
return strcmp(book->author,author);
}
int Book_CompareNum(Book *book,int num)
{
return book->num-num;
}
//Program.c
#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)와 결과가 비슷한 것을 알 수 있습니다.
알고리즘 성능을 분석할 때 수학적으로 계산해서 증명할 수 있으면 좋겠죠. 만약 그렇지 못한다면 지금처럼 실제 수행 시간을 측정하여 비교해 보세요.
'언어 자료구조 알고리즘 > 디딤돌 정렬 알고리즘 (C언어)' 카테고리의 다른 글
3.2 선택 정렬 알고리즘 구현 (0) | 2016.11.24 |
---|---|
3.1 선택 정렬 알고리즘 성능 분석 (0) | 2016.11.24 |
3. 선택 정렬(Selection Sort) 알고리즘 (0) | 2016.11.24 |
2.3 버블 정렬 알고리즘 소스 (0) | 2016.11.24 |
2.2 버블 정렬 알고리즘 구현 (0) | 2016.11.24 |
2.1 버블 정렬 알고리즘 성능 분석 (0) | 2016.11.24 |
2. 버블 정렬(Bubble Sort) 알고리즘 (0) | 2016.11.24 |
1.2 순차 정렬 알고리즘 구현 (0) | 2016.11.24 |
1.1 순차 정렬 알고리즘 성능 분석 (0) | 2016.11.24 |
1. 순차 정렬(Sequential Sort) 알고리즘 (0) | 2016.11.24 |