삽입 정렬

func insertionSort(array: inout [Int]){
    for i in 1 ..< array.count {
        let temp = array[i]
        var index = i - 1
        while(index >= 0 && array[index] >= temp){
            array[index+1] = array[index]
            index -= 1
        }
        array[index+1] = temp
    }
}

시작할 때 맨 앞의 요소는 정렬된 것으로 간주하고, 나머지는 정렬되지 않은 것으로 간주한다.

정렬되지 않은 요소를 차례로 탐색하여 정렬된 요소 가운데 적절한 위치에 삽입한다.