[디딤돌 자료구조와 알고리즘 with C] 2.3.2 선택 정렬 알고리즘 구현

2.3.2 선택 정렬 알고리즘 구현

선택 정렬 알고리즘.zip

이제 선택 정렬 알고리즘을 구현합시다.

 

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

{

 먼저 내부 반복문과 외부 반복문에서 사용할 두 개의 변수를 선언하세요.

    int i = 0, j=0;

 그리고 최대값이 있는 위치를 기억할 변수도 선언합니다. 그리고 교환에서 사용할 임시 변수도 선언하세요.

    int max=0;

    Element temp;

 외부 반복문에서는 정렬할 범위를 점진적으로 줄여나갑니다.

    for(i=n; i>1; i--)

    {

 내부 반복문에서는 max를 0으로 초기화하고 j를 1로 초기화합니다. 이는 일단 맨 앞에 있는 요소를 최대값이 있는 위치로 설정하고 그 다음 요소부터 최대값과 비교하기 위해서입니다. 그리고 j는 순차적으로 다음 인덱스로 이동합니다.

        for(max=0, j=1; j<i; j++)

        { 

 만약 max인덱스의 요소보다 j인덱스의 요소가 더 크면 두 개의 max를 j로 설정합니다.

            if(compare(base[max],base[j])<0)

            {

                max = j;

            }

        }

 내부 반복문을 수행한 후에 최대값이 있는 max인덱스 요소와 정렬할 범위의 마지막 위치에 있는 요소를 교환합니다. 정렬할 원소 개수가 i일 때 마지막 위치의 요소는 i-1을 주의하세요.

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

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

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

    }

}

 

 위 알고리즘을 테스트하는 코드는 버블 정렬과 같습니다. 여기에서는 설명을 생략할게요. 다만 시뮬레이션 함수의 bubble_sort 함수 호출을 select_sort 함수 호출로 변경하세요.

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

}

 

▷ 실행 결과

--------제목순-------

<0000006334>:<0000000041>

              저자:0000018467

<0000017421>:<0000000292>

              저자:0000012382

<0000011942>:<0000000491>

              저자:0000002995

<0000032391>:<0000004827>

              저자:0000005436

<0000026962>:<0000011478>

              저자:0000029358

<0000000153>:<0000014604>

              저자:0000003902

<0000019895>:<0000018716>

              저자:0000019718

<0000009961>:<0000023281>

              저자:0000016827

<0000028145>:<0000024464>

              저자:0000005705

<0000015724>:<0000026500>

              저자:0000019169

--------번호순-------

<0000000153>:<0000014604>

              저자:0000003902

<0000006334>:<0000000041>

              저자:0000018467

<0000009961>:<0000023281>

              저자:0000016827

<0000011942>:<0000000491>

              저자:0000002995

<0000015724>:<0000026500>

              저자:0000019169

<0000017421>:<0000000292>

              저자:0000012382

<0000019895>:<0000018716>

              저자:0000019718

<0000026962>:<0000011478>

              저자:0000029358

<0000028145>:<0000024464>

              저자:0000005705

<0000032391>:<0000004827>

              저자:0000005436

1000개 정렬에 걸린 시간:103

10000개 정렬에 걸린 시간:7923

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

}

2.3.1 선택 정렬 알고리즘

2.3.2 선택 정렬 알고리즘 구현