[Algorithm] Insertion Sort, 삽입 정렬

What is it

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

다시 말해, 배열에서 기준으로 삼은 요소의 자리를, 앞에 정렬된 배열 안에서 기준 요소보다 작은 요소와 큰 요소 사이에 삽입해준다고 생각하면 된다.!

맨 처음 비교를 시작할 때는 앞에 정렬된 배열이 없으므로, 기준 요소는 배열의 2번째 요소부터 시작한다.

출처 - https://visualgo.net/en/sorting

How to works it

삽입 정렬을 하기 위해서는 두개의 for문이 필요하다.!
하나는 정렬된 배열의 마지막 요소를 가리킬 for문과
나머지 하나는 기준 요소를 감소시키며 바로 앞 요소와 비교할 for문!

아래의 그림을 참고하며 이해해보자!

Let's make it Code

1. for sortedIndex in 0..<arr.count - 1로 반복
2. for standardIndex in stride(from: sortedIndex + 1, to: 0, by: -1) 로 기준 요소의 인덱스를 1씩 감소하며 반복
3. 내부 반복문 안에서 arr[standardIndex] < arr[standardIndex - 1] 이면 swap

func insertionSort(_ array: Array<Int>) -> Array<Int> {
    var arr = array
    
    for sortedIndex in 0..<arr.count - 1 {
        for standardIndex in stride(from: sortedIndex + 1, to: 0, by: -1){
            if arr[standardIndex] < arr[standardIndex - 1] {
                arr.swapAt(standardIndex, standardIndex - 1)
            }else{
                break
            }
        }
    }
    return arr
}

print(insertionSort([5,3,2,7,4]))	//2, 3, 4, 5, 7

알고리즘 분석

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