삽입 정렬

1. 개념

• 새로운 숫자가 삽입될 때 정렬된 배열 안에서 자신의 위치를 찾아가며 정렬하는 알고리즘

2. 구현 (kotlin)

fun insertionSort(arr: IntArray) {
    for (i in 1 until arr.size) { // i = 현재 정렬된 배열의 크기
        val key = arr[i]
        var j = i - 1 // 정렬된 배열에서 제일 큰 숫자의 인덱스(가장 오른쪽에 있는 숫자의 인덱스)
        while (j >= 0 && arr[j] > key) { // 정렬된 배열에서 제일 큰 숫자의 인덱스부터 0번 인덱스까지 비교하면서 현재 값이 key보다 크면,
            arr[j + 1] = arr[j] // 현재 값을 한 칸 오른쪽에 덮어 씌운다.
            j -= 1
        }
        arr[j + 1] = key // 올바른 위치에 key 삽입
    }

    arr.forEach {
        print("$it ")
    }
}

3. 정렬 과정

4. 시간복잡도와 공간복잡도

시간복잡도

• Best

  • 오름차순으로 정렬되어 있는 경우, 내부 while문이 동작하지 않으므로, O(N)의 시간복잡도를 가진다.

• Worst

  • 내림차순으로 정렬되어 있는 경우, 매번 내부 while문이 동작하므로, O(N²)의 시간 복잡도를 가진다.

공간복잡도

• 별도의 추가 공간을 사용하지 않고, 주어진 배열 내에서 값의 위치만 바뀌기 때문에 O(1)의 공간 복잡도를 가진다.

면접 예상 질문

1. 삽입 정렬의 시간복잡도를 Best, Worst 케이스로 나눠 설명해주세요.
2. 삽입 정렬을 구현해주세요.

참고 URL

https://youtu.be/iqf96rVQ8fY?si=O83YiZU4ni9QWKOa
https://chlgpdus921.github.io/algorithm/sort/insertion