[알고리즘] 선택 정렬(Selection Sort)

선택 정렬 정의

선택 정렬은 n개의 데이터 중에서 최소값을 찾아 첫 번째 데이터 위치에 놓고, 나머지 (n-1)개 중 다시 최소값을 찾아 두 번째 데이터 위치에 놓는 방식을 반복하여 정렬하는 방식이다.

즉, 한 번의 회전에 모든 데이터를 확인해봐야 한다.

구현

package datastructure

fun main() {
    val list = mutableListOf(5, 8, 6, 2, 4)
    selectionSort(list)
}

private fun selectionSort(list: MutableList<Int>) {
    for(i in 0 until list.size) {
        for(j in i+1 until list.size) {
            if(list[i] > list[j]) {
                swap(list, i, j)
            }
        }

        println("${i+1}회전: $list")
    }
}

private fun swap(list: MutableList<Int>, idx1: Int, idx2: Int) {
    val temp = list[idx1]
    list[idx1] = list[idx2]
    list[idx2] = temp
}

구현 결과

시간복잡도

정렬 과정을 보면, 각 회전마다 현재 위치와 그 이후의 위치에 있는 모든 데이터를 비교한다.

이를 코드로 보면 이중 for문이 사용되는 것을 확인할 수 있다.

즉, O(n²)의 시간복잡도를 갖게 된다.