개념 요약
- Bubble Sort와 유사한 알고리즘이다.
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있으며 어떤 원소를 넣을지 선택하는 알고리즘이다.
정렬 과정
- 주어진 배열 중 최솟값을 찾는다.
- 찾은 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
코드
void selection_sort(std::vector<int> &unsorted_array)
{
int temp = 0, min_idx = 0, max = unsorted_array.size();
// 위치 지정 인덱스
for (int i = 0; i < max - 1; ++i)
{
// 현재 인덱스값 지정
min_idx = i;
for (int j = i + 1; j < max; ++j)
{
// 대소 비교
if (unsorted_array[j] < unsorted_array[min_idx])
min_idx = j;
}
// swap
temp = unsorted_array[min_idx];
unsorted_array[min_idx] = unsorted_array[i];
unsorted_array[i] = temp;
}
}
시간 복잡도
- 거품 정렬과 동일한 방식으로 최선, 평균, 최악의 경우에 $O(n^2)$이다.
공간 복잡도
- 주어진 배열 내에 교환으로 정렬이 수행되므로 $O(n)$이다.
장단점
- 알고리즘이 단순하며, 배열 내부에서 swap 하는 방식으로 추가 메모리가 필요 없다.
- 비효율적이고 불안정한 정렬이다.
'CS공부 > Algorithm' 카테고리의 다른 글
힙 정렬(Heap Sort) (0) | 2022.06.21 |
---|---|
병합 정렬(Merge Sort) (0) | 2022.06.21 |
퀵 정렬(Quick Sort) (0) | 2022.06.20 |
삽입 정렬(Insertion Sort) (0) | 2022.06.20 |
거품 정렬(Bubble Sort) (0) | 2022.06.20 |