[Algorithm] 선택 정렬 (Selection Sort)

Selection Sort

• 각 루프마다 남아있는 원소 중 가장 큰 원소를 선택한 후, 남아있는 원소 중 맨 오른쪽 원소와 바꿈
• 교환된 수는 다음 루프에서 제외
• 하나의 원소가 남을 때까지 반복

코드

배열의 크기가 10으로 고정되어있다고 가정하고 작성한 코드이다.

#include <iostream>

void Print(int* arr)
{
    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

void SelectionSort(int* arr)
{
    for (int i = 9; i > 0; i--)
    {
        int maxNum = arr[0];
        int maxIdx = 0;

        for (int j = 0; j <= i; j++)
        {
            if (arr[j] > maxNum)
            {
                maxNum = arr[j];
                maxIdx = j;
            }
        }

        std::swap(arr[i], arr[maxIdx]); // 맨 오른쪽과 스왑
    }
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);

    int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};

    Print(arr);
    SelectionSort(arr);
    Print(arr);
}

시간 복잡도

평균과 최악 모두 O(n^2)의 시간 복잡도를 가진다.

참고사항

교환하는 원소에 따른 오름/내림차순 여부

• 최대값 → 맨 오른쪽 교환 ⇒ 오름차순
• 최대값 → 맨 왼쪽 교환 ⇒ 내림차순
• 최소값 → 맨 오른쪽 교환 ⇒ 내림차순
• 최소값 → 맨 왼쪽 교환 ⇒ 오름차순

• 입력 배열 외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다.
• 기존 배열에 정렬 결과와 관계 없이 항상 일정한 시간 복잡도를 가짐 -> 입력에 민감하지 않은 (input insensitive) 알고리즘