Insertion Sort Swift

오늘은 Insertion Sort 를 Swift 로 간단하게 구현해보도록 하겠습니다.

 

시간복잡도는 O(n^2) 으로 최적화된 정렬은 아닙니다만, 가장 간단하게 구현할 수 있는 정렬 중 하나라고 할 수 있겠습니다.

 

func insertionSort(_ arr: [Int]) -> [Int] {  // O(n^2)
    
    var a = arr
    
    for i in 1..<a.count {

        var j = i

        while j > 0 && a[j] < a[j - 1]{
            a.swapAt(j-1, j)
            j -= 1
        }
    }
  
    return a
    
}

 

Swift 문법을 통해서는 아래처럼 조금 더 간편하게 변경할 수 있습니다.

 

func insertionSort(_ arr: [Int]) -> [Int] {  // O(n^2)
    
    var a = arr
    
    for var i in 1..<a.count {
            
        while i > 0 && a[i] < a[i - 1]{
            a.swapAt(i-1, i)
            i -= 1
        }
    }
    
    return a
    
}