선택 정렬에 대해서 다뤄보겠습니다!

선택 정렬(Selection Sort)

저는 단순하게 0번째부터 length - 1까지 시작해 해당 인덱스에 적절한 원소를 넣어 정렬한다로 이해했어요. 방식을 오름차순 기준으로 설명드리자면,

1. i번째 인덱스부터 시작하여 i+1부터 쭉 확인해서 가장 작은 원소의 인덱스를 찾습니다.
2. i번째 원소와 가장 작은 원소가 위치한 인덱스번째 원소와 교환합니다.
   2-1. 이렇게 되면 i번째 원소는 위치가 정해졌어요. 이를 length - 1까지 반복하면 정렬이 완료가 됩니다.

그림

특징

선택 정렬Selection Sort도 버블 정렬Bubble Sort와 마찬가지로 $O(n^{2})$입니다. 버블 정렬과 달리 교환 횟수가 비교적 적은 편(인덱스를 정하고 교환)이라 버블 정렬보단 효율적여요.

또한 따로 배열이 추가로 필요하지 않다고 해서 In-place하다는 특징이 있습니다. 하지만 정확한 위치에 있는 원소도 교환이 일어나는 경우가 있어 Unstable한 정렬이기도 합니다.

소스

template<typename T>
class SelectionSort
{
public:
	static void sort(vector<T>& arr)	
	{
		if(arr.size() <= 1)	return;

		int minIndex = 0;
		for(int i = 0; i < arr.size() - 1; ++i)
		{
			minIndex = i;
			for(int j = i + 1; j < arr.size(); ++j)
			{
				if(arr[j] < arr[minIndex])
					minIndex = j;
			}
			swap(arr[i], arr[minIndex]);
		}
	}
};