선택 정렬(Selection Sort)

선택 정렬 이란?

주어진 리스트 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다.
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
시간복잡도는 O(n^2) 이다.

선택 정렬 과정

리스트의 배열 0~4번까지 순차적으로 돌면서 제일 작은 숫자의 찾아 인덱스를 저장한다.

이때 3의 인덱스를 가지게 된다.

위에서 찾은 3번의 인덱스를 0번의 인덱스를 참조해 교체한다.

0번의 인덱스는 제외하고 1~4번까지 다시 순차적으로 돌면서 제일 작은 숫자의 인덱스를 저장한다.

이때 2의 인덱스를 가지게 된다.

위에서 찾은 2번의 인덱스를 1번의 인덱스를 참조해 교체한다.

0,1번의 인덱스는 제외하고 2~4번까지 다시 순차적으로 돌면서 제일 작은 숫자의 인덱스를 저장한다.

이때 3번의 인덱스를 가지게 된다.

위에서 찾은 3번의 인덱스를 2번의 인덱스를 참조해 교체한다.

이런 과정을 통해 정렬을 할 수 있다.

선택 정렬 코드

#include <iostream>

int main()
{
    int Array[5] = { 4,3,2,1,5 };

    int Count = 5;

    int Index = 0;

    for (int i = 0; i < Count; ++i)
    {
        Index = i;
        for (int j = i + 1; j < Count; ++j)
        {
            if (Array[Index] > Array[j])
            {
                Index = j;
            }
        }
        int Temp = Array[Index];
        Array[Index] = Array[i];
        Array[i] = Temp;
    }


    for (int i = 0; i < Count; ++i)
    {
        std::cout << Array[i] << " ";
    }
}