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

선택정렬(Selection Sort)

선택 정렬(Selection Sort)은 버블정렬(Bubble Sort)와 같은 시간복잡도(O(n2))를 가지지만, 

버블 정렬과는 조금 달리 불안정(Unstable)한 알고리즘 입니다. 무슨말이냐면, 

예를 들어 {8, 7, 5, 5, 6} 이 있을 경우 정렬한 후에 5와 5의 위치가 바뀔수도 있다는 거랍니다.

즉, 같은 내용을 가지는 키 값들이 정렬 후에도 순서가 유지되는걸 말합니다.

선택정렬은 다음과 같은 과정을 거칩니다.

< [ 8, 2, -1, 5, 4 ] 선택정렬 >

선택 정렬(Selection Sort) 알고리즘은 최초 한 값을 선택하고, 다른 값들과 비교한 후 작은 값이 있으면

그 값을 저장하고 마지막까지 갔다면, 최초 선택한 값과 스왑하는 방식입니다.

글로 쓰니까 어렵네요. 그림이 도움이 될꺼에요.(시간상 2, 3회전은 스킵하였습니다)

< C++ 코드 >

#include 
using namespace std;

void selectionSort(int arr[], int n)
{
	int minIndex = 0;
	for(int i = 0; i < n -1; i++)
	{
		minIndex = i;
		for(int j = i + 1; j < n; j++)
		{
			if(arr[minIndex] > arr[j])
				minIndex = j;
		}

		if( minIndex != i)
		{
			int temp = arr[minIndex];
			arr[minIndex] = arr[i];
			arr[i] = temp;
		}
	}
}

int main()
{
	int values[] = {8, 2, -1, 5, 4};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	selectionSort(values, 5);
	cout << "After sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

참고 : http://www.algolist.net/