정렬 알고리즘 #1. 선택 정렬 (Selection Sort)

설명

선택정렬은 현재 위치에 들어갈 값을 찾아 배열을 정렬한다.

현재 위치에 저장되는 값에 따라 최소 선택 정렬(Min-Selection)와 최대 선택정렬(Max-Selection)로 나뉜다

기본 로직

1. 정렬되지 않은 Array의 Index의 맨 앞을 대상으로 이후 가장 작은 값을 찾는다 (최솟값 찾기)
2. 가장 작은 값을 찾으면, 현재 Index의 위치의 값과 바꾼다
3. 다음 Index에서 위 1, 2번 과정을 반복한다

시간 복잡도

n-1개, n-2개, ..., 1개의 비교를 반복한다. 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다

 

 

코드 (C++)

void SelectionSort(vector<int> v)
{
	for(int i = 0; i < v.size()-1; i++)
    {
    	int temp = i;
        for(int j = i+1; j < v.size(); j++)
        {
        	if(v[temp] >= v[j]) 
            	temp = j;
        }
        swap(v[i], v[temp]);
    }
}