언어 자료구조 알고리즘/디딤돌 정렬 알고리즘 (C언어)

3.2 선택 정렬 알고리즘 구현

언제나휴일 2016. 11. 24. 16:42
반응형

3.2 선택 정렬 알고리즘 구현


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

 

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

반응형