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
'언어 자료구조 알고리즘 > 디딤돌 정렬 알고리즘 (C언어)' 카테고리의 다른 글
4.3 삽입 정렬 알고리즘 소스 코드 (0) | 2016.11.25 |
---|---|
4.2 삽입 정렬 알고리즘 구현 (0) | 2016.11.25 |
4.1 삽입 정렬 알고리즘 성능 분석 (0) | 2016.11.25 |
4. 삽입 정렬(Insertion Sort) 알고리즘 (0) | 2016.11.25 |
3.3 선택 정렬 알고리즘 소스 (0) | 2016.11.24 |
3.1 선택 정렬 알고리즘 성능 분석 (0) | 2016.11.24 |
3. 선택 정렬(Selection Sort) 알고리즘 (0) | 2016.11.24 |
2.3 버블 정렬 알고리즘 소스 (0) | 2016.11.24 |
2.2 버블 정렬 알고리즘 구현 (0) | 2016.11.24 |
2.1 버블 정렬 알고리즘 성능 분석 (0) | 2016.11.24 |