1. 선택 정렬 (Selection Sort)
ㅇ 매 반복 패스 마다,
- 가장 큰/가장 작은 자료를 선택(select)하고,
- (즉, 찾아서, 위치를 기억하고 있다가)
ㅇ 해당 반복 패스가 끝날 때,
- 이를 맨앞/맨뒤로 옮기는(교환하는) 과정을 수행
- (이 과정에서, 순서대로 정렬된, 리스트로써 나타남)
ㅇ 전체 자료에 대해,
- 이러한 과정을 반복적으로 수행
2. 선택 정렬의 특징
ㅇ 키(Key)에 의해 이루어지고, 사실상 필요시에 만 교환 됨
ㅇ 제자리 정렬 (in-place sort)
- 입력 배열 외에 추가적인 메모리가 불필요
. 단, 교환 동작 수행을 위한 임시 1개 필요 => O(1)
- 입력 배열 그 자체를 사용하여 정렬시키고, 그 정렬된 배열을 그대로 반환
ㅇ 안정적이지 못한 정렬 (nonstable sort)
- 정렬 전 입력 자료 순서가 유지되지 못함
ㅇ 기본 연산 둘 : 비교 연산, 교환 연산
- 비교 필요 횟수 : 총 n(n-1)/2회의 데이터 비교가 필요함 => O(n2)
. 설사 정렬되어 있더라도, 무조건 n(n-1)/2회의 데이터 비교가 필요함
. 즉, (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 ≤ n2
- 교환 필요 횟수 : 총 n-1 반복 패스 중 n-1번 교환 필요함 => O(n)
ㅇ 시간복잡도 : O(n2)
- 입력 데이터 상태가 어떻든지간에 언제나 동일한 수행 시간 O(n2)을 갖음
ㅇ 데이터량이 적을때는, 비교적 좋은 성능을 보임
3. 선택 정렬의 방법
ㅇ 2개의 중첩 루프를 사용
- 외부 루프는, 남은 배열의 첫 요소부터 마지막까지 반복
. 정렬 대상이 되는 배열의 크기를 하나씩 줄여주는 역할을 함
- 내부 루프는, 해당 배열의 다음(나머지 첫) 요소부터 마지막까지 반복
ㅇ 즉,
- 처음과 나머지 자료들과 비교하면서,
- 제일 큰/작은 자료를 맨 오른쪽/왼쪽에 두도록, 위치 교환
- 직후 자료와 그 나머지 자료들과 비교,위치 교환을 반복해가며, 정렬해나감
4. 프로그래밍 例 (C 언어)
/* 선택정렬 (오름차순) */
Input : (정렬 전 데이터 배열) A[], (배열 데이터 수) int n
Output : (정렬 후 데이터 배열) A[]
void SelectionSort(int A[], int n) {
int outer, inner, min, temp;
for (outer = 0; outer < n-1; outer++) {
min = outer;
for (inner = outer + 1; inner < n; inner++) {
if (A[inner] < A[min]) {
min = inner;
}
}
// 교환 : A[outer] ↔ A[min]
temp = A[min];
A[min] = A[outer];
A[outer] = temp;
}
}