나동빈님의 실전 알고리즘 강좌(Algorithm Programming Tutorial)를 바탕으로 학습한 내용을 정리한 포스트입니다.
실습 코드는 WebKit’s style guide를 따라 C언어로 작성되었습니다.
개인적으로 학습하며 작성한 포스트이기 때문에 오류가 있을 수 있습니다. 잘못된 내용이 있다면 댓글로 알려주세요.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#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]);
    }

    return 0;
}

개요

선택 정렬은 배열에서 가장 작은 값을 찾아 맨 앞부터 채워나가는 방식의 정렬입니다.
소스코드에서 min은 가장 작은 숫자를 임시로 저장하는 변수이고, temp는 배열에서 두 숫자의 위치를 서로 바꾸기 위해 사용하는 변수입니다.

시간 복잡도

길이가 10인 배열을 정렬할 때 선택 정렬을 사용하는 경우 10+9+8+...+1=55번 배열에 접근합니다.

이러한 등차수열은 N*(N+1)/2 즉, 10*(10+1)/2로 구하는 방법도 있는데, N이 매우 큰 숫자일 경우 +1과 /2는 의미가 큰 의미가 없기 때문에 일반적으로 N*N번 접근한다고 이야기합니다.

이를 Big-O 표기법으로 표기하면 O(N*N) => O(N²)이 됩니다.

결론: 선택 정렬의 시간 복잡도는 O(N²)이다.