[정렬 알고리즘] 선택 정렬(Selection Sort)

선택 정렬은 정렬 알고리즘의 한 방법입니다.

버블 정렬과 마찬가지로 간단한 정렬 알고리즘에 속합니다.

가장 작은(혹은 큰) 값을 찾아서 맨 앞(혹은 맨 뒤)로 차곡차곡 이동시키는 방법입니다.

기본적으로 생각할 수 있는 방법으로 정렬합니다.

선택 정렬의 코드는 다음과 같습니다.

#include <iostream>
using namespace std;

template <class T>
void MySwap(T& a, T &b)
{
	T tmpVal = a;
	a = b;
	b = tmpVal;
}

template <class T>
void SelectionSort(T* arVal, int nCount)
{
	int maxidx;
	int i, j;

	for (i = nCount - 1 ; i >= 0 ; --i)
	{
		for (maxidx = i, j = i - 1 ; j >= 0 ; --j)
		{
			if (arVal[maxidx] < arVal[j])
				maxidx = j;
		}
		if (maxidx != i)
			MySwap(arVal[maxidx], arVal[i]);
	}
}

int main()
{
	int arNoSort[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	for (int i = 0; i < sizeof(arNoSort) / sizeof(int); ++i)
	{
		cout << arNoSort[i] << " ";
	}
	cout << endl;

	SelectionSort(arNoSort, sizeof(arNoSort) / sizeof(int));

	for (int i = 0; i < sizeof(arNoSort) / sizeof(int); ++i)
	{
		cout << arNoSort[i] << " ";
	}
	cout << endl;
}

C++의 템플릿 버전입니다.

위의 코드는 가장 큰 값을 기준으로 맨 뒤로 이동시키는 코드입니다.

약간만 수정하면 가장 작은 값을 앞으로 이동시키는 방법을 사용할 수도 있습니다.

맨 뒤에서 앞까지 이동하면서 가장 큰 값의 위치를 찾습니다.

그리고 맨 앞까지 이동해서 가장 큰 값의 위치가 확정되면 가장 큰 값과 맨 뒤의 값의 위치를 변경합니다.

맨 뒤의 값은 이미 가장 큰 값이기 때문에 그 앞부터 이동하면서 다시 가장 큰 값을 찾습니다.

다시 찾았으면 맨 뒤의 값 앞에 위치시킵니다.

값이 맨 뒤를 기준으로 차곡차곡 이동하는 것을 확인할 수 있습니다.

간단한 정렬 알고리즘이기 때문에 이해하는 것이 어렵지는 않을 것입니다.