정의
- 리스트에 원소를 넣을 위치를 정해두고, 어떤 원소를 넣을지 선택하는 알고리즘
- 거품 정렬 (Bubble sort)과 유사
- 제자리 정렬 알고리즘 : 정렬되지 않은 값들 이외에 다른 추가 메모리를 요구하지 않는 정렬알고리즘 & 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택함
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택함
과정 (내림차순)
- 리스트에서 최소값인 요소를 찾는다
- 최소값을 맨 앞의 요소와 교체
- 맨 앞의 요소를 제외하고 같은 과정을 반복
코드
void selectionSort(int[] A, int n)
{
int indexMin, temp;
for(int i = 0; i < A.length - 1; i++) {
indexMin = i;
for (int j = i + 1; j < A.length; j++) {
if (A[j] < A[indexMin]) {
indexMin = j;
}
}
temp = A[indexMin];
A[indexMin] = A[i];
A[i] = temp;
}
}
시간복잡도
- 비교 횟수
최악, 평균, 최선 모두 : (n - 1) + (n - 2) + ... + 3 + 2 + 1 = n(n-1) / 2
- 교환 횟수
회당 한 번 씩 : n - 1
# T(n) = O(n ^ 2)
- 매개변수가 정렬이 되었는지와 상관없이 무조건 비교하므로 최악, 평균, 최선 모두 동일
출처
https://devuna.tistory.com/28