삽입정렬

삽입 정렬 (insertion sort) 란

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

func insertionSort(unSortedArray: [Int]) -> [Int] {
    var unSortedArray = unSortedArray
    for index in 0..<unSortedArray.count - 1 {
        for index2 in stride(from: index + 1, to: 0, by: -1) {
            if unSortedArray[index2-1] > unSortedArray[index2] {
                let temp = unSortedArray[index2]
                unSortedArray[index2] = unSortedArray[index2-1]
                unSortedArray[index2-1] = temp
            } else {
                break
            }
        }
    }
    return unSortedArray
}

삽입 정렬은 두번째 인덱스 부터 시작하니, 총 사이클 수는 정렬해야할 배열 수에서 1를 뺀 값이다. (첫번째 for문)

본격적으로 인덱스2(두번째 인덱스부터 비교시작) 앞에 있는 데이터들을 비교하며 정렬을 해나가는 과정이 두번째 for문 로직이다.