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

선택정렬은 '가장 작은 원소를 앞으로 보내는' 알고리즘 방법입니다.

 

두 번의 For Loop를 사용하며 배열을 순회하며 min(최솟값)을 찾아서 그 값을 배열의 맨 앞으로 보내고 해당 값 이후의 인덱스부터 다시 최솟값을 찾아서 비교하며 정렬하게 됩니다.

 

O(N^2)의 시간 복잡도를 가지는 구현이 단순하지만 비효율적인 알고리즘입니다.

 

func selectionSort(notSortedArray: [Int]) -> [Int] {
    /* for swap
     var temp: Int
     */
    var index: Int
    var array: [Int] = notSortedArray
    
    for i in 0 ..< notSortedArray.count { //External Loop
        var min: Int = array[i]
        index = i
        
        for j in i + 1 ..< array.count { //Internal Loop
            if (min > array[j]) {
                min =  array[j]
                index = j
            }
        }
        
        /* for swap
         temp = notSortedArray[i]
         notSortedArray[i] = notSortedArray[index]
         notSortedArray[index] = temp
         */
        array.swapAt(i, index)
    }
    
    return array
}

print(selectionSort(notSortedArray: notSortedArray))


// 출력
[1, 2, 3, 4, 5, 6, 7, 8, 9]

 

External Loop는 최솟값이 놓일 인덱스를 위해 사용하고

Internal Loop는 최솟값을 구한 인덱스 이후의 배열 중 다시 최솟값을 찾기 위해서 사용합니다.

 

Internal Loop에서 최솟값을 찾았다면 배열에서 해당 최솟값의 index를 저장해놓고, External Loop에서 해당 값을 현재 인덱스의 값과 Swap하는 작업을 반복하며 정렬을 하게 됩니다.

 

 

* Swift에서 제공하는 array.swapAt() 함수를 사용하지 않고 직접 값을 swap해주는 방법도 있습니다.

for swap으로 주석처리된 부분을 보면

현재 인덱스의 값을 temp라는 값에 저장해놓고, 

현재 인덱스의 값에 min값을 가지는 인덱스의 값을 넣어줍니다.

그 후 min값의 저장되어있던 인덱스에 temp의 값을 넣어줍니다.

 

a -> b

b -> c

c -> a 

의 구조로 swap을 직접 구현할 수 있습니다.