[ALGORITHM] 17. 선택 정렬 구현하기

선택 정렬(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. 다른 정렬 알고리즘에 비해 성능이 낮다 : 버블정렬처럼 원소의 이동이 빈번하게 발생하기에

다른 정렬 알고리즘보다 성능이 낮다.