[디딤돌 자료구조와 알고리즘 with C] 2.2.2 순차 정렬 알고리즘 구현

2.2.2 순차 정렬 알고리즘 구현

순차정렬알고리즘.zip

이번에는 순차 정렬 알고리즘을 구현해 보기로 해요.

순차 정렬(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개의 원소가 있는 배열의 주소와 원소 개수 및 비교 알고리즘을 입력 인자로 필요합니다.

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

 

 시뮬레이션을 하기 위해 필요한 초기 작업을 수행하는 함수를 작성합시다.

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

}

 

 수행 속도를 확인하기 위한 시뮬레이션 함수도 작성합시다.

void Simulation2()

{

 속도를 확인하기 위해 clock_t 변수를 두 개 선언합니다. 하나는 정렬을 수행하기 전의 시간을 기억하기 위한 변수이고 하나는 수행한 후의 시간을 기억하기 위한 변수입니다. 참고로 clock_t 형식은 시스템에서 자원 사용에 관한 회계를 위해 정의한 논리적 시간으로 운영체제에 따라 단위가 다릅니다. 여기에서는 상대적인 시간을 비교하기 위함이므로 단위가 얼마인지는 중요하지 않습니다.

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

 

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