삽입 정렬 (Insertion Sort)

목표

• Insertion Sort에 대해 설명할 수 있다.
• Insertion Sort 과정에 대해 설명할 수 있다.
• Insertion Sort를 Kotlin으로 구현할 수 있다.
• Insertion Sort의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다.

요약

Insertion Sort는 Selection Sort와 비슷하여 헷갈릴 수 있지만 좀 더 효율적인 정렬 알고리즘이다.

Insertion Sort는 2번째 요소부터 시작하여 그 앞의 요소들과 대소 비교하여 삽입할 위치를 지정한 후 삽입할 위치 이후의 요소들을 한 칸씩 뒤로 미루면서 삽입하는 정렬 알고리즘이다.

최선의 경우에는 O(N) 이라는 빠른 효율성을 가지고 있어 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.

과정 (오름차순)

1. 두 번째 요소를 그 앞의 요소(첫 번째 요소)들과 비교하여 삽입할 위치를 찾아 해당 위치에 넣는다.
2. 세 번째 요소를 그 앞의 요소(두 번째, 첫 번째 요소)들과 비교하여 삽입할 위치를 찾아 해당 위치에 넣는다.
3. N 번째 요소까지 반복한다.

Kotlin 코드

fun insertionSort() {
    val lst = mutableListOf(1, 34, 5, 6, 78, 23, 56, 31, 64)
    for (i in 1 until lst.count()) {
        val temp = lst[i]
        for (j in i - 1 downTo 0) {
            if (lst[j] < lst[i]) {
                lst[j + 1] = temp
                break
            } else {
                lst[j + 1] = lst[j]
            }
        }
    }
    println(lst)
}

시간 복잡도

1. 최악의 경우(역으로 정렬 된 경우)

• 비교 횟수 : 외부 루프 안의 각 반복마다 i번의 비교 수행
  • (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

2. 최선의 경우

• 비교 횟수 : 이동 없이 1번의 비교만 이루어진다.
  • (n-1)번 = O(n)

공간 복잡도

기존에 주어진 배열에서 원소 Swap만 이루어지므로 공간 복잡도는 O(n)이다.

특징

장점

1. 알고리즘 구현이 비교적 단순하다.
2. 대부분의 원소가 이미 정렬되어 있는 경우에 효율적이다.
3. 주어진 배열에서만 교환하므로 다른 메모리 공간이 필요하지 않다. => 제자리 정렬(in-place sorting)
4. 안정 정렬이다.
5. 다른 O(n^2) 알고리즘에 비해 상대적으로 빠르다.

자체 테스트(단위 : 나노초)
버블 정렬 시간 : 11658800
선택 정렬 시간 : 57300
삽입 정렬 시간 : 33000

단점

1. 시간 복잡도가 평균, 최악에서는 O(n^2)로 굉장히 비효율적이다.

Reference

• https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%82%BD%EC%9E%85%20%EC%A0%95%EB%A0%AC%20(Insertion%20Sort).md#%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-insertion-sort
• https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html