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

안녕하세요!! @wonnieyoon입니다.
오늘의 포스팅 주제는 컴퓨터 알고리즘 중 '선택정렬'입니다.

정렬이란? 특정 기준으로 줄을 세우는것이라 볼수 있습니다.
선택정렬이란?
먼저 정렬 알고리즘 중에 가장 느린 정렬입니다.
순차적으로 가장 작은것을 젤 앞에 보내는 정렬이라고 생각하시면 될듯 합니다.
반대로 가장 큰것을 젤 앞에 보내는 정렬이라고 생각하셔도 됩니다.

선택정렬이란 ?
오름차순이라면 제일 작은수를 선택해서 앞으로 보내는 방법,
내림차순이라면 가장 큰수를 선택해서 앞으로 보내는 방법

※선택정렬
<소스코드>

int main()
{
int data[6] = { 7, 5, 3, 1, 8, 4 };
int position = 0;

for (int i = 0; i < 6; i++)
{
    int tempMin = INT_MAX;
    for (int j = i; j < 6; j++)
    {       
        if (tempMin > data[j])
        {
            tempMin = data[j];
            position = j;
        }
    }

    int temp = data[i];
    data[i] = data[position];
    data[position] = temp;
}

for (int i = 0; i < 6; i++)
{
    cout << data[i] << "\t";
}

return 0;

}
<출력결과>

코드를 보시면 알겠지만 특별히 어렵지는 않습니다.
하지만 데이터가 있다면 모든 데이터를 읽으면서 가장 작은수를 찾기 때문에
만약 데이터가 100개 있다면
처음에는 100개, 두번째는 99개, 세번째는 98, .....마지막은 1개 순으로 검색을 하게 됩니다.

등차수열이기 때문에 100 * (100+1) / 2 로 나타낼수 있고
이것은 N * (N + 1) / 2 라고 할수 있습니다.
결국 컴퓨터에서는 +1 , /2 는 수가 커지면 큰 영향을 미치지 않기 때문에
선택 정렬의 시간 복잡도는 O(N^2) 가 됩니다.

선택정렬 시간복잡도 : O(N^2)