[자료구조] 선택 정렬(Selection sort)

선택 정렬은 다음과 같은 단계를 따른다.

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다. 한 셀씩 이동하면서 현재까지 가장 작은 값을 변수에 저장한다. 변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다.

2. 이제 최솟값이 어느 인덱스에 들어 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다. 패스스루를 시작했을 때 인덱스는 첫 패스스루에서 인덱스 0일 것이고, 두 번째 패스스루에서는 인덱스 1일 것이다.

3. 데이터가 모두 정렬될 때까지 1, 2단계를 반복한다.

#include <vector>
using namespace std;

void selectionSort(vector<int>& array)
{
	for (int i = 0; i < (int)array.size(); i++)
	{
		int minValIndex = i;
		for (int j = i + 1; j < (int)array.size(); j++)
		{
			if (array[j] < array[minValIndex])
				minValIndex = j;
		}
		if (minValIndex != i)
		{
			int temp = array[i];
			array[i] = array[minValIndex];
			array[minValIndex] = temp;
		}
	}
}

int main()
{
	vector<int> vArr = { 2, 6, 1, 3 };
	selectionSort(vArr);

	for (int i = 0; i < (int)vArr.size(); i++)
		cout << vArr[i] << endl;
	return 0;
}

  선택 정렬은 비교와 교환, 두 종류의 단계를 포함한다. 즉, 각 패스스루 내에서 각 원소를 현재까지 찾은 최솟값과 비교하고, 최솟값을 올바른 위치에 있는 수와 교환한다. 5개의 원소를 포함하는 배열을 예로 들면 총 10번의 비교를 해야 했다. 

  이와 달리 교환은 한 패스스루 당 최대 한 번 일어난다. 배열이 역순으로 정렬된 최악의 시나리오에서는 버블 정렬과 달리 비교할 때마다 빠짐없이 교환을 한 번 해야 한다. 선택 정렬은 분명 버블 정렬보다 단계 수가 반 정도 적다. 즉, 선택 정렬이 두 배 더 빠르다.