언어 자료구조 알고리즘/디딤돌 정렬 알고리즘 (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

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