Nagie's DevStory
[ALGORITHM] 17. 선택 정렬 구현하기 본문
728x90
선택 정렬(Selection Sort)은 리스트를 순회하면서 가장 작은 값을 찾아 리스트의 앞으로 옮기는 방식으로 동작한다.
template<typename T>
void selection_sort(std::vector<T>& data) { // O(n^2)
int n = data.size();
for (int i = 0; i < (n - 1); i++) {
int idx = i;
for (int j = (i + 1); j < n; j++) {
if (data[j] < data[idx]) {
idx = j;
}
}
std::swap(data[i], data[idx]);
}
}
특징
1. 간단한 구현 : 버블정렬과 같이 간단하게 구현할 수 있는 정렬 알고리즘이며,
반복문을 사용해 작은 값을 선택 후 앞으로 옮기는 방식으로 동작한다.
2. 불안정 정렬 알고리즘 : 동일한 값의 원소 간의 상대적인 순서가 정렬 후 유지되지 않을 수 있다.
장점
1. 작은 데이터셋에서 효과적 : 작은 데이터셋에 대해서는 다른 정렬 알고리즘보다 성능이 크게 떨어지지 않을 수 있다.
단점
1. 비효율적인 성능 : 평균 및 최악의 경우 시간 복잡도가 O(n²)이기 때문에 큰 데이터셋에 대해서는 비효율적이다.
2. 다른 정렬 알고리즘에 비해 성능이 낮다 : 버블정렬처럼 원소의 이동이 빈번하게 발생하기에
다른 정렬 알고리즘보다 성능이 낮다.
728x90
Comments