• 선택 정렬은 버블 정렬과 마찬가지로 제자리정렬임.
• 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하여 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있음.
• 배열 자료구조를 사용함.

알고리즘

1. 주어진 리스트에서 최솟값을 찾음.
2. 그 값을 맨 앞에 위치한 값과 교체함.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체.

예시

정렬되지 않은 배열로 가정하고, 오름차순으로 정렬 프로세스로 가정. → [5, 3, 4, 1, 2]

1. 배열의 최솟값 찾기 → [1]
2. 첫 번째 자리와 교체 → [1, 3, 4, 5, 2]
3. 나머지 원소에서 최솟값 찾기 → [3, 4, 5, 2] → 2
4. 첫 번째 자리와 교체 → [2, 4, 5, 3]
5. 나머지 원소에서 최솟값 찾기 → [4, 5, 3] → 3
6. 정렬될 때 까지 반복.

소스코드 - Kotlin

fun main() {
    println(selectionSort(intArrayOf(5, 3, 4, 1, 2)))
}

fun selectionSort(intArray: IntArray) {
    for(i in intArray.indices) {
        var currentIndex = i
        for(j in i+1 until intArray.size) {
            if(intArray[currentIndex] > intArray[j]) currentIndex = j // 최솟값 찾기
        }
        // 맨 앞과 교체
        val temp = intArray[currentIndex]
        intArray[currentIndex] = intArray[i]
        intArray[i] = temp
    }
}

범위 및 함수 사용시 유의사항

• indices : IntRange타입을 반환하며**,** 수신객체의 전체 범위 반환. 위 예제 에선 0..4