[C언어 소스] 선택 정렬 (Selection Sort) 알고리즘

이번에는 반복 알고리즘일 이용하는 선택 정렬 알고리즘을 알아봅시다.

선택 정렬 알고리즘은 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘입니다. 물론 제일 작은 값을 찾아 맨 앞의 요소와 교체하는 방법을 반복할 수도 있습니다.

선택 정렬 알고리즘을 의사코드(pseudo code: 논리적인 수행 흐름을 이해할 수 있게 작성한 코드)는 다음과 같습니다.

알고리즘

선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리)

    반복(i:=n;  i>1  ; i:= i-1)

        반복(max=0,j:=1; j<i ; j:=j+1)

            조건(compare(base[max], base[j]) < 0)

                max := j

        temp: = base[i-1]

        base[i-1] = base[max]

        base[max] = temp

선택 정렬 알고리즘
선택 정렬 알고리즘

점근식 계산

이번에는 선택 정렬 알고리즘 성능을 분석합시다.

선택 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 i+1에서 n까지 순차적으로 증가하므로 비교를 n-i번 수행함을 알 수 있어요. 따라서 S(i)= n-i죠.

외부 반복문은 i가 0에서 n까지 순차적으로 증가하면서 내부 반복문을 수행하고 교환 1회합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 이죠.

따라서 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 = n+1 + n + n-1 + …+1

따라서 T(n)= n(n+1)/2 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 선택 정렬도 순차 정렬과 거품 정렬처럼 O(n^2)이네요.

하지만 교환하는 시간은 O(n)이라는 차이가 있어요. 물론 전체 성능에 미치는 영향은 아주 작아요.

소스 코드