삽입 정렬

맨 왼쪽의 원소는 이미 정렬되어 있다고 가정하고,

두번째 원소부터 시작해서 왼쪽으로 순차적으로 현재 원소보다 큰 원소가 있다면 교체를 해주고,

또 다음 반복에서 그 왼쪽의 원소와 비교하여 또 큰 원소가 있다면 교체를 해주고,

이 작업을 반복하다가 마침내 현재 원소의 왼쪽 원소가 현재 원소보다 작은 경우를 만날 시에

브레이크로 중단하는 정렬 방식입니다.

 

fun main() {
    val arr = intArrayOf(2,5,3,1,6,7,0,4,8,9)

    for(i in 1 until arr.size) {
        for(j in i downTo 1) {
            if(arr[j] < arr[j-1]) {
                val temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
            }
            else
                break
        }
    }

    println(arr.contentToString())
}

 

필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 효율적인 방식입니다.

시간복잡도는 O(n^2)이며, 이미 배열이 모두 정렬되어 있는 최상의 경우에는 O(n)의 시간복잡도를 가집니다.