[Algorithm#01] | 선택 정렬(Selection Sort)

🎓 동빈나님의 강의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 듣고 정리한 내용입니다.

 

💻 알고리즘

선택 정렬(Selection Sort)

• 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘
• 가장 원시적이고 기초적인 방법 중 하나

 

📝 문제

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

 

✏️ 소스 코드

#include <stdio.h>

int main(void)
{
    int
    i, j,  /*배열에 있는 원소를 반복적으로 탐색하기 위한 필드*/
    min,   /*최솟값(가장 작은 원소를 선택하기 위한 필드)*/
    index, /*가장 작은 원소가 존재하는 위치*/
    temp;  /*특정한 두 숫자를 서로 바꾸기 위한 필드*/

    // 탐색할 원소 배열
    int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

    for (i = 0; i < 10; i++)
    {
        // 아주 큰 값을 넣는 이유 : 항상 최솟값을 선택하기 위해 탐색할 모든 원소들 보다 커야한다.
        min = 9999;

        for (j = i; j < 10; j++)
        {
            // 최솟값 고르기
            if (min > array[j])
            {
                min = array[j];
                index = j;
            }
        }
        // 스와핑을 한다.
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }
    // 정렬 확인
    for (i = 0; i < 10; i++)
    {
        printf("%d ", array[i]);
    }
}

 

⏳ 시간 복잡도

선택 정렬의 시간 복잡도는 O(N^2)입니다.

중요한 것은 데이터의 갯수가 N개일 때 총 몇 번의 비교 연산을 해야 되는지입니다. 선택 정렬은 대략 N * (N + 1) / 2 번 가량의 연산을 수행해야 합니다. 이를 컴퓨터에서는 가장 큰 차수인 N^2만 보고 O(N^2)이라고 표현하곤 합니다.

1 2 3 4 5 6 7 8 9 10

10 + 9 + 8 + 7 + ... + 1

=> 10 * (10 + 1) / 2 = 55
=> N = (N + 1) / 2 <--- 일반적으로 컴퓨터에선 N이 매우 크다는 가정 하에 간단하게 나누거나 더하는 연산들은 무시합니다.
=> N * N
=> O(N * N)(=O(N^2))

다시 말해 정렬해야 할 데이터의 갯수가 10,000 개라면 대략 일 억 번 정도 계산을 한다고 가정을 하겠다는 의미입니다. 실제로 이 정도의 시간 복잡도를 가지는 선택 정렬이 효율적인지, 그리고 현실 세계의 정렬 상황에서 효과적으로 사용될 수 있을지 고민해보는 시간을 가져봅시다.

 

📚 참고 사이트

• 동빈나 블로그
• 동빈나 - 실전 알고리즘 강좌 (Algorithm Programming Tutorial)