[Algorithm] 삽입 정렬(Insertion Sort) 이란? (feat.Swift)

안녕하세요 Foma💻  입니다!

 

오늘은 학교 알고리즘 수업을 듣는 중에 삽입 정렬을 구현해보는 과제가 있었는데... 

 

딱 이 방식이 어떤 것이고 어떻게 구현해야 한다! 라고 구체적으로 떠오르지가 않더라구요... 

 

그래서 삽입 정렬이 무엇이고 어떻게 구현해야 하는지에 대해 정리해보려고 합니다!

 

바로 시작할게요~

---

삽입 정렬이란?

 

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. -위키 백과 -

 

정렬하는 과정을 살펴보면 아래와 같습니다.

 

출처: 위키백과

 

삽입 정렬 과정

 

82,10,9,72,31,45,60를 삽입 정렬을 하는 과정은 아래와 같습니다.

 

1. 먼저 맨 첫 번째인 82와 그 다음 숫자인 10을 비교해줍니다. 

 

10이 더 작으므로 82 앞으로 보냅니다. <- 10 82

 

2. 10 다음 숫자인 9와 10 82를 비교해줍니다.

 

9는 10,82보다 작으므로 가장 앞으로 보냅니다 <- 9 10 82

 

3. 그 다음 숫자인 72와 이전 숫자들을 비교해줍니다.

 

72는 82보다 작고 10보다 크므로 10 바로 뒤로 보내줍니다. <- 9 10 72 82

 

4. 31과 이전 숫자들을 비교합니다.

 

31은 72보다 작고 10보다 크므로 10 바로 뒤로 보내줍니다. <- 9 10 31 72 82

 

5. 45와 이전 숫자들을 비교합니다.

 

45는 31보다 크고 72보다 작으므로 31 뒤로 보내줍니다. <- 9 10 31 45 72 82

 

6. 마지막으로 60과 이전 숫자들을 비교합니다.

 

60은 45보다 크고 72보다 작으므로 45 뒤로 보내줍니다. <- 9 10 31 45 60 72 82

 

시간복잡도

 

만약 n개의 데이터가 있다면, 최악의 경우 처음부터 끝까지 1 + 2 + 3 + 4 ... n-1까지 비교를 해야 하기 때문에

 

시간 복잡도는 O(n²)입니다.

 

 

---

코드 구현

 

import Foundation

var numbers = [82,10,9,72,31,45,60]

numbers.sortByInsertion(nil)

extension Array where Element == Int {
    mutating func sortByInsertion(_ startIndex:Int?) -> [Int] {
        let start = startIndex == nil ? 1 : startIndex!
        if start == self.count { return self }
        
        let current = self.remove(at: start)
        var index = 0
        for i in stride(from: start-1, through: 0, by:-1) {
            if current >= self[i] {
                index = i+1
                break
            }
        }
        self.insert(current, at:index)
        return sortByInsertion(start+1)
    }
}