Page 210 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

단순 선택 정렬의 교환 과정은 아래와 같습니다.

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택합니다.
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환합니다.

이 과정을 n - 1회 반복하면 됩니다. 이 과정을 간략한 코드로 나타내면 다음과 같습니다.

for(i = 0; i < n - 1; i++) {
//min = a[i], …, a[n – 1]에서 가장 작은 값을 가지는 요소의 인덱스
//a[i]와 a[min]의 값을 교환
}

실습 6-4는 단순 선택 정렬 함수입니다.

실습 6-4는 단순 선택 정렬 함수 부분의 코드만 본문에 실었습니다. 실습 6-1의 main 함수에서 bubble 함수를 selection
함수로 바꾸어 실행하세요.

실습 6-4 •완성 파일 chap06/selection.c

01 /*--- 단순 선택 정렬 ---*/
02 void selection(int a[], int n)
03 {
04 int i, j;
05 for(i = 0; i < n - 1; i++) {
06 int min = i;
07 for(j = i + 1; j < n; j++)
08 if(a[j] < a[min])
09 min = j;
10 swap(int, a[i], a[min]);
11 }
12 }

단순 선택 정렬 알고리즘의 요솟값을 비교하는 횟수는 (n - n) / 2회입니다. 그런데 이 정렬
2
알고리즘은 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않습니다. 그림
6-11은 안정적이지 않은 정렬을 수행할 때의 모습입니다. 그림 6-11을 보면 값이 3인 요소
가 중복해서(2개) 있을 때 두 요소의 순서가 뒤바뀌는 것을 알 수 있습니다.

R
L
같은 값을 가진 두 요소를 구별하기 위해 정렬하기 전의 앞쪽에 있는 요소를 3 , 뒤쪽에 있는 요소를 3 로 표시했습니다.

210 C 알고리즘