Insertion Sort (삽입 정렬)

Insertion Sort (삽입 정렬)은 이름 그대로 적절한 위치에 삽입을 하여 정렬을 하는 알고리즘입니다. 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 하나씩 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성합니다. 요소를 하나씩 비교해나가기 때문에 시간 복잡도는 O(n^2)를 가집니다.

 

 

알고리즘 구현 순서는 다음과 같습니다.

1. 비교는 배열의 두 번째 인덱스부터 시작하여 자신의 앞쪽에 있는 요소들과 비교합니다.
2. 비교했을 때, 앞의 요소가 자신보다 크다면 swap 합니다.
3. 비교했을 때, 앞의 요소가 자신보다 작다면 비교를 멈춥니다.
4. 다음 인덱스의 요소부터 다시 2~4를 반복합니다.

 

 

 

아래는 Swift로 구현한 Insertion Sort 입니다.

var arr: [Int] = [5,2,4,1,3]

for i in 1..<arr.count {
    var index = i
    for j in stride(from: i-1, to: -1, by: -1) {
        if arr[j] <= arr[index] { break }
        list.swapAt(index, j)
        index -= 1
    }
}

print(arr) // [1,2,3,4,5]