이번 시간에는 선택정렬에 대해 알아보자
과정 설명
선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다
1회전:
첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.
2회전:
두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.
3회전:
세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.
4회전:
네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.
# include <stdio.h>
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
# define MAX_SIZE 5
// 선택 정렬
void selection_sort(int list[], int n) {
int i, j, least, temp;
// 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
for (i = 0; i < n - 1; i++) {
least = i;
// 최솟값을 탐색한다.
for (j = i + 1; j < n; j++) {
if (list[j] < list[least])
least = j;
}
// 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
if (i != least) {
SWAP(list[i], list[least], temp);
}
}
}
void main() {
int i;
int n = MAX_SIZE;
int list[n] = { 9, 6, 7, 3, 5 };
// 선택 정렬 수행
selection_sort(list, n);
// 정렬 결과 출력
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}
자료 이동 횟수가 미리 결정된다.
안정성을 만족하지 않는다.
즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.
시간복잡도를 계산한다면
두 개의 for 루프의 실행 횟수
외부 루프: (n-1)번
내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번
외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번
T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)