자료구조와 알고리즘 - 언제나 휴일

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

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

——–번호순——-