언어 자료구조 알고리즘/[C]디딤돌 자료구조와 알고리즘

[디딤돌 자료구조와 알고리즘 with C] 2.4.2 삽입 정렬 알고리즘 구현

언제나휴일 2016. 4. 10. 10:22
반응형

2.4.2 삽입 정렬 알고리즘 구현


 삽입 정렬 알고리즘을 구현합시다. 시뮬레이션 함수 등은 앞과 같으므로 설명을 생략할게요.


void insertion_sort(Element *base, int n, Compare compare)

{

 두 개의 반복문에서 사용할 변수를 선언하고 교환에 사용할 임시 변수도 선언할게요.

    int i = 0, j=0;

    Element temp;

 외부 반복문은 정렬할 범위를 넓혀나가는 것입니다. 따라서 i 1부터 n까지 점진적으로 증가할게요.

    for(i=1; i<n; i++)

    {

 내부 반복문은 새롭게 범위에 포함한 원소의 위치를 찾아야 합니다. 따라서 j i로 초기화하고 점진적으로 줄여나갑니다.

        for(j=i; j>0; j--)

        {

 만약 j번째 원소가 앞의 원소보다 크면 자리를 교환합니다.

            if(compare(base[j-1],base[j])<0)

            {

                temp = base [j-1];

                base[j-1] = base [j];

                base[j] = temp;

            }

 그렇지 않을 때는 반복문을 탈출합니다.

            else{    break;    }

        }

    }

}

 

 다음은 삽입 정렬 알고리즘과 이를 테스트 하는 소스 코드 내용입니다.

 

#include "common.h"

#include "Book.h"

typedef void *Element;

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

 

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

{

    int i = 0, j=0;

    Element temp;

    for(i=1; i<n; i++)

    {

        for(j=i; j>0; j--)

        {

            if(compare(base[j-1],base[j])<0)

            {                                 

                temp = base [j-1];

                base[j-1] = base [j];

                base[j] = temp;

            }

            else

            {

                break;

            }

        }

    }

}

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

{

    insertion_sort(books,10,CompareByTitle);

    printf("--------제목순-------\n");

    ListBook(10);

    insertion_sort(books,10,CompareByNum);

    printf("--------번호순-------\n");

    ListBook(10);

}

void Simulation2()

{

    clock_t st,et;

    st = clock();

    insertion_sort(books,MAX_BOOK/10,CompareByTitle);

    et=clock();

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

    st = clock();

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

}


2.4 삽입 정렬 알고리즘

반응형