All that Sort - [3] Selection Sort (선택정렬)

선택정렬! 단도직입적으로 말하면, n번째 자리에 맞는 수를 찾아서 n번째 자리에 넣는 정렬이다.

in-place 정렬이고 O(n2)의 복잡도를 가지는데, 위에서 설명한 것처럼, 좀 무식한-_-방법으로 sorting을 하기 때문에 bubble sort 보다 아주 약~간 뛰어나지만 insertion sort 보다는 "일반적으로" 좋지 못한 성능을 보인다.

어찌됐든, pseudocode 를 봅시다.

1 for i = 0 to n-2 do

2     min = i

3     for j = i+1 to n-1 do

4        if (a[j] < a[min]) do

5           min = j

6     if(i != min) do

7        swap a[i] and a[min]

그림에서와 같이 첫자리에 맞는 수 2, 둘째 자리에 맞는 수 3, 그리고 4, 5 이렇게 각 자리에 맞는 수를 끝.까.지. 찾는다.