[알고리즘] 삽입정렬

삽입정렬(Insertion sort)

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여(뒤에서 앞으로 비교), 자신의 위치를 찾아 삽입하는 정렬 알고리즘
• 두번째 인덱스(1번 인덱스)부터 시작

설명	0	1	2	3	4	-
ex)	5	2	4	3	1
1번 자리의 2가 그 앞의 5보다 작으므로 자리를 바꾼다	2	5	4	3	1	실행횟수 = 1
다시 반복	-	-	-	-	-	반복횟수 = 1
2번 자리의 4가 그 앞의 5보다 작으므로 자리를 바꾼다	2	4	5	3	1
1번 자리의 4는 그 앞의 2보다 크므로 자리를 바꾸지 않는다	2	4	5	3	1	실행횟수 = 2
다시 반복	-	-	-	-	-	반복횟수 = 2
3번 자리의 3이 그 앞의 5보다 작으므로 자리를 바꾼다	2	4	3	5	1
2번 자리의 3이 그 앞의 4보다 작으므로 자리를 바꾼다	2	3	4	5	1
1번 자리의 3은 그 앞의 2보다 크므로 자리를 바꾸지 않는다	2	3	4	5	1	실행횟수 = 3
다시 반복	-	-	-	-	-	반복횟수 = 3
4번 자리의 1이 그 앞의 5보다 작으므로 자리를 바꾼다	2	3	4	1	5
3번 자리의 1이 그 앞의 4보다 작으므로 자리를 바꾼다	2	3	1	4	5
2번 자리의 1이 그 앞의 3보다 작으므로 자리를 바꾼다	2	1	3	4	5
1번 자리의 1이 그 앞의 2보다 작으므로 자리를 바꾼다	1	2	3	4	5	실행횟수 = 4
끝	1	2	3	4	5	반복횟수 = 4

• 배열의 길이 = 5
• 실행횟수 = 1 -> 2 -> 3 -> 4
• 반복횟수 = 4

일반화

• 배열의 길이 = n
• 실행횟수 = 1 -> 2 -> ... -> n-2 -> n-1
• 반복횟수 = n-1

특징

• 반복할 때 뒤에서부터 앞으로(거꾸로) 숫자 크기 비교
• 숫자의 크기를 비교할 때 비교할 숫자보다 크다면 그때의 반복문은 종료

구현

1. for stand in range(len(data)-1)로 반복
2. for num in range(stand+1, 0, -1) 반복
   • 내부 반복문 안에서 data_list[num] < data_list[num-1] 이면,
     • data[num], data[num-1] = data[num-1], data[num]

---

Python

def insertion_sort(data):
    for stand in range(len(data)-1):
        for num in range(stand+1, 0, -1):
            if data[num] < data[num-1]:
                data[num], data[num-1] = data[num-1], data[num]
            else:
                break
    return data

Swift

import Foundation

func insertionSort(_ data: [Int]) -> [Int] {
    var data = data
    for stand in 0..<(data.count - 1) {
        for num in (1...(stand + 1)).reversed() {
            if data[num] < data[num-1] {
                data.swapAt(num, num-1)
            } else {
                break
            }
        }
    }
    return data
}

시간복잡도

• 반복문이 2개이므로 $O(n^2)$
  • 최악의 경우, ${n(n-1)\over 2}$
• 완전 정렬이 되어 있는 상태라면 최선의 경우, $O(n)$