[CS] 알고리즘 04 : 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

선택정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.

선택 정렬의 동작과정

선택 정렬의 시간복잡도

선택 정렬의 시간복잡도는 O(n²)이다.

선택 정렬 코드 (Swift)

func selectionSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    
    for i in 0..<arr.count {
        var min = i
        for j in i+1..<n {
            if arr[j] < arr[min] {
                min = j
            }
        }
        arr.swapAt(i, min)
    }
    return arr
}

let arr = [3, 7, 1, 8, 4]
print(selectionSort(arr))

선택 정렬 개선 코드 (Swift)

func selectionSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    
    for i in 0..<arr.count {
        var min = i
        for j in i+1..<n {
            if arr[j] < arr[min] {
                min = j
            }
        }
        if min != i {
            arr.swapAt(i, min)
        }
    }
    return arr
}