1.3 순차 정렬 알고리즘 소스

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)와 결과가 비슷한 것을 알 수 있습니다.

 

알고리즘 성능을 분석할 때 수학적으로 계산해서 증명할 수 있으면 좋겠죠. 만약 그렇지 못한다면 지금처럼 실제 수행 시간을 측정하여 비교해 보세요.