2.4.3 선택 정렬 알고리즘 소스 코드

//common.h

#pragma once //헤더 파일을 한 번만 포함해서 컴파일

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

#include <malloc.h>

#include <memory.h>

#include <time.h>

#pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제

 

//Book.h

#pragma once

#include “common.h”

#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);

 

//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(book->title,title,MAX_TIT_LEN);

strncpy(book->author,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 “common.h”

#include “Book.h”

typedef void *Element;

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

 

void select_sort(Element *base, int n, Compare compare)//선택 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

{

int i = 0, j=0;

int max=0;

Element temp;

for(i=n; i>1; i–)//    반복(i:=컬렉션의 자료 개수;  i>1  ; i:= i-1)

{

for(max=0, j=1; j<i; j++)//반복(max=0,j:=1; j<i ; j:=j+1)

{

if(compare(base[max],base[j])<0)//조건(icomparer(collection[max], collection[j]) < 0)

{

max = j;//max := j

}

}

temp = base[i-1];//temp: = collection[i-1]

base[i-1] = base[max];//collection[i-1] = collection[max]

base[max] = temp;//collection[max] = temp

}

}

#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(title,”%010d”,rand());

sprintf(author,”%010d”,rand());

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

}

}

int CompareByTitle(void *b1,void *b2)

{

Book *book1=(Book *)b1;

Book *book2=(Book *)b2;

return Book_CompareTitle(book1,book2->title);

}

int CompareByNum(void *b1,void *b2)

{

Book *book1=(Book *)b1;

Book *book2=(Book *)b2;

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()

{

select_sort(books,10,CompareByTitle);

printf(“——–제목순——-\n”);

ListBook(10);

select_sort(books,10,CompareByNum);

printf(“——–번호순——-\n”);

ListBook(10);

}

void Simulation2()

{

clock_t st,et;

st = clock();

select_sort(books,MAX_BOOK/10,CompareByTitle);

et=clock();

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

st = clock();

select_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;

}