삽입 정렬은 간단하지만 효율적인 정렬 알고리즘입니다. 정렬되지 않은 배열에서 한 요소씩 선택하여 이미 정렬된 부분과 비교하고 적절한 위치에 삽입하는 방식으로 동작합니다. 이번 포스트에서는 Swift에서 삽입 정렬 알고리즘을 구현하는 방법을 알아보겠습니다.

알고리즘 구현

func insertionSort(_ array: inout [Int]) {
    guard array.count > 1 else { return }
    
    for i in 1..<array.count {
        let key = array[i]
        var j = i
        
        while j > 0 && array[j - 1] > key {
            array[j] = array[j - 1]
            j -= 1
        }
        
        array[j] = key
    }
}

위의 코드는 입력으로 받은 배열 array를 삽입 정렬하는 함수입니다. 함수의 입력 파라미터 array는 inout으로 정의되어 배열이 직접 수정되도록 합니다.

알고리즘은 배열의 두 번째 요소부터 시작하며, 현재 요소를 key 변수에 저장합니다. j 변수를 사용하여 이미 정렬된 부분과 비교하고 삽입 될 위치를 찾아갑니다. 만약 j가 0보다 크고 array[j - 1]이 key보다 크다면, array[j]와 array[j - 1]을 교환하고 j를 감소시킵니다. 이 과정을 반복하여 key 값을 올바른 위치에 삽입한 후, 다음 요소로 넘어갑니다.

사용 예제

var numbers = [5, 3, 7, 1, 2]
insertionSort(&numbers)
print(numbers) // [1, 2, 3, 5, 7]

위의 예제에서는 정렬되지 않은 숫자들이 담긴 배열을 생성하고, insertionSort 함수를 호출하여 정렬합니다. 마지막으로 정렬된 배열을 출력하여 확인합니다.

시간 복잡도

삽입 정렬의 시간 복잡도는 O(n^2)입니다. 외부 루프는 n번 반복하고, 내부 루프는 최악의 경우 현재 인덱스까지 모든 요소와 비교하므로 최대 n번 반복됩니다. 따라서 삽입 정렬은 작은 배열이나 거의 정렬된 배열에 적합합니다.

결론

Swift에서 삽입 정렬 알고리즘을 구현하는 방법을 살펴보았습니다. 삽입 정렬은 간단하면서도 효율적인 알고리즘으로 작은 배열이나 거의 정렬된 배열에 적합합니다. 이를 활용하여 정렬 문제에 유용하게 활용할 수 있습니다.