사진 출처 : 올바른 선택을 위한 7가지 원칙

특징

• 제자리 정렬 알고리즘
• 앞쪽부터 순서대로 바꿀 위치를 선택한 후 그 자리에 오는 값을 찾는 알고리즘
• 탐색을 할 때 동일값에 대해 정렬 순서가 바뀔 수 있는 불안정 정렬에 속함

알고리즘

1. 주어진 리스트 중 최소값을 먼저 찾음
2. 그 값을 맨 앞에 위치한 값과 교체
3. 교체된 위치를 제외한 나머지를 같은 방법으로 반복
   

장단점

장점
- 구현이 쉬운 편에 속함
- 비교하는 횟수는 많으나 실제로 교환하는 횟수는 적어 교환 횟수가 많은 자료상태에서는 비교적으로 효율적임

단점
- 데이터를 하나씩 비교하기 때문에 시간이 오래 골림
- 정렬된 상태에서 새로운 데이터가 추가 될 경우에 효율이 좋지 않음

복잡도

시간복잡도
- 데이터 n개를 검색할 경우 검색 횟수가 (n-1) + (n-2) + ... + 1이 되므로 최종적으로 n(n-1)/2
- 이때 시간복잡도는 O(n2)가 나옴

공간복잡도
- 주어진 배열 내에서 교환이 이루어지므로 O(n)

소스코드

fun main(args: Array<String>) {
    val array = arrayOf(5, 7, 3, 4, 1, 9, 2, 6, 8)
    var index: Int
    var temp: Int
    for(i in array.indices) {
        index = i
        for(j in i + 1 until array.size){
            if(array[index] > array[j])
                index = j
        }

        temp = array[i]
        array[i] = array[index]
        array[index] = temp
    }
    print(array.contentToString())
}

Reference

• 선택 정렬(Selection Sort)
• 선택 정렬 - 위키백과, 우리 모두의 백과사전