C++ / Algorithm 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)이란 제자리 정렬 알고리즘 중 하나로 정렬되지 않은 데이터들 중에서 

가장 작은 값을 추출해 가장 맨 앞으로 정렬해나가는 알고리즘입니다.

 

1. 배열 중 최소값을 찾습니다.

2. 최소값을 맨 앞으로 정렬합니다. (Swap)

3. 나머지 값들도 같은 매커니즘으로 정렬합니다.

 

알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우, 사용에 이점이 있으며, 

구현이 간단하지만 비효율적인 알고리즘입니다. 

예시

선택 정렬 시간 복잡도

 

기준값과 비교값들 중 최소값을 찾기 위해 이중 for문이 필요합니다.

- 첫 번째 회전 비교 횟수 : 1부터 (n-1) = n-1 

- 두 번째 회전 비교 횟수 : 2부터 (n-1) = n-2

... 

-> 최소값 찾기 : n-1, n-2, ... 2, 1 번

T(n) = (n-1) + (n-2) + ... + 2+ 1 = n(n-1) /2 = O(n^2) 

 

int main()
{
	int n, tmp, idx, a[100];

	scanf("%d", &n);

	for(int i = 0; i < n ; i ++)
	{
		scanf("%d", &a[i]);
	}

	for(int i = 0; i < n-1; i++)
	{
		// 비교 기준값을 잡기 위한 idx 변수를 사용합니다.
		idx = i;

		// 기준값 다음 블록의 요소와 비교하기 위해 j 를 i+1로 초기화합니다.
		for(int j = i+1; j < n; j++)
		{
			if(a[j] < a[idx])
			{
				// 처음 기준값은 i 이지만 배열을 순차적으로 순회하며 
                //  idx값, 즉 기준값이 변경될 수 있습니다. i 가 변경되는 것이 아니니 안심하세요.
                //  작은 요소들을 발견할 때마다 idx 를 업데이트합니다.
                
				idx = j;
			}
		}
        // 위 과정을 거쳐 가장 작은 값의 idx 를 저장했기 때문에 비교 기준 인덱스와 Swap합니다.
			tmp = a[i];
			a[i] = a[idx];
			a[idx] = tmp;
	}

	for(int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}

    return 0;
}