[알고리즘][KOTLIN] 선택 정렬

정의

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

코드

fun main(args: Array<String>) {
    // INPUT  : [42, 32, 24, 60, 15]
    // OUTPUT : [15, 24, 32, 42, 60]
    val result = selectedSort(intArrayOf(42, 32, 24, 60, 15))

    result.forEach { r ->
        print("$r ")
    }
}

private fun selectedSort(arr: IntArray): IntArray {
    // 배열의 최소 값을 찾는다.
    var index = 0

    while (index != arr.size) {
        var min = Int.MAX_VALUE
        var target = 0

        for (i in index until arr.size) {
            if (min > arr[i]) {
                min = arr[i]
                target = i
            }
        }

        // 최소값으로 찾은 값과 배열의 index 값과 위치를 바꾼다.
        val temp = arr[index]
        arr[index] = min
        arr[target] = temp

        // 최소값을 앞에 채웠기 때문에 index 를 증가 시킨다.
        index++
    }

    return arr
}