선택정렬 (Selection Sort)

키 값을 선택하여 값을 이동한다.

오름차순으로 정렬시 제일 먼저 제일 작은 값이 와야하므로 데이터 내에서 가장 작은 키 값을 선택하여 제일 앞으로 보낸다.

나머지 데이터에서 가장 작은 값을 찾아서 이미 정렬된 키 값 다음 위치로 보낸다.

반복하여 제일 마지막 키 값이 남을 때까지 작은 키 값을 찾아 이미 정렬된 키 값 다음 위치로 보내는 동작을 반복한다.

마지막 키 값은 정렬되지 않아도 위치가 확정이므로 정렬이 끝난다.

비교 연산 : 두 개의 루프. 1. n개 만큼 비교 시작. 2. n-1개와 비교. 즉 비교에 n(2) 만큼의 효율.

이동 연산 : 두 값의 위치 변경. temp 변수 포함 3번의 이동 연산. 즉 이동에 3n = n 만큼의 효율.

최종 n(2)+n 이므로 O(n(2))의 효율을 지닌다.

상대적으로 느린 알고리즘. 

이동 연산 자체는 n의 효율이므로 이동해야하는 데이터가 큰 경우 유리하다.

데이터가 이동이 계속 되므로 불안정성 정렬이다.

// 선택 정렬 함수
void SelectionSort(int data[], int cnt)
{
    int minIndex = 0, temp = 0;
    int i = 0, j = 0;
 
    // 첫번째 루프 : n-1만큼 비교
    for (i = 0; i < cnt - 1; i++)
    {
        minIndex = i;
 
        // 두번째 루프 : n개만큼 비교
        for (j = i + 1; j < cnt; j++)
        {
            if (data[j] < data[minIndex])
            {
                minIndex = j;
            }
        }
 
        // 이동 연산 : 3n
        if (minIndex != i)
        {
            temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }
    }
}