[알고리즘] 삽입 정렬(Insertion Sort)

삽입 정렬 정의

삽입 정렬은 정렬 알고리즘 중 가장 간단한 정렬 방식이다.

앞에서부터 차례대로 비교해가며, 자신의 위치를 찾아 삽입함으로써 정렬이 완성된다.

삽입 정렬은 두 번째 데이터부터 시작하여 그 앞에 있는 데이터와 비교하여 삽입할 위치를 지정한 후 데이터를 뒤로 옮기며, 이후 지정한 위치에 데이터를 삽입한다.

구현

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

private fun insertionSort(list: MutableList<Int>) {
    for(i in 1 until list.size) {
        val key = list[i]
        var j = i-1

        while(j >= 0 && key < list[j]) {
            list[j+1] = list[j]
            j--
        }

        list[j+1] = key

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

구현 결과

시간복잡도

정렬 과정과 구현 코드를 확인해보면, n번을 반복하며, 그 안에서 키(m)까지 또 반복이 일어나는 것을 확인할 수 있다.

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

만약 이미 정렬되있는 배열이라면, 최선의 경우로 O(n)의 시간복잡도를 갖는다.