얌생

선택 정렬( Selection Sort )은 버블 정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 선택 정렬과 삽입 정렬를 헷갈릴 수 있는데, 선택 정렬은 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 된다.

선택 정렬은 3가지의 과정을 반복하며 정렬을 수행한다.

 1. 선택한 곳의 데이터보다 더 작은 데이터가 있는지 순환하며 찾는다.

 2. 구한 가장 작은 최솟값을 맨 앞에 위치한 값과 교체한다.

 3. 맨 앞의 위치를 하나씩 앞으로 옮겨가며 반복한다.

#include<iostream>
using namespace std;

int main()
{
	int Array[] = { 10,9,8,7,6,5,4,2,3,1 };
	int MinIndex;
	int Number;

	for (int i = 0; i < 9; i++)
	{
        // 맨 앞 위치 선택
		MinIndex = i;

		for (int j = i + 1; j < 10; j++)
		{
            // 선택한 위치 값과 다른 위치 값들비교
            // 더 작은 값이 있으면 위치값 갱신
			if (Array[MinIndex] > Array[j])
			{				
				MinIndex = j;
			}
		}
        
        // 한번 반복하고 나면 스왑
		swap(Array[i], Array[MinIndex]);
	}

	return 0;
}

시간복잡도

데이터의 개수가 n개라고 할 경우,

• 첫 번째 회전에서의 비교횟수 : 1 ~ ( n - 1 ) => n - 1
• 두 번째 회전에서의 비교횟수 : 2 ~ ( n - 1 ) => n - 2
• ...
• (n-1) + (n-2) + ... + 2 + 1 => n(n-1) / 2

비교하는 것이 상수 시간에 이루어진다는 가정 아래에서 n개의 주어진 배열을 정렬하는데

O( n^2 ) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O( n^2 )로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.