선택 정렬
집합 안에서 최소값을 찾아서 최소값을 앞(왼쪽)으로 보내는 방식입니다. 반대로 최대값을 뒤(오른쪽)으로 보내는 방식도 있습니다.
원리
⓵ 기준 원소를 포함해서 최소값을 탐색합니다.
⓶ 기준 원소보다 작은 최소값이 있다면 기준 원소와 자리를 바꿉니다.
⓷ 다음 원소로 옮겨서 탐색을 진행합니다.
*정렬할 원소가 없을 때까지 반복
예시
선택 정렬을 그림으로 나타내봤습니다. 주어진 배열 [9, 7, 2, 13, 10] 를 선택 정렬을 사용해서 정렬해보겠습니다.
⓵, ⓸ 은 기준 원소보다 작은 최소값이 존재합니다.
⓶, ⓷ 은 기준 원소보다 작은 값이 존재하지 않습니다. 따라서 별 다른 원소 교환이 일어나지 않습니다.
SelectionSort.swift
저는 선택 정렬 코드를 이렇게 구현해봤습니다. 밑에서 자세하게 설명해보겠습니다.
func swap(a: Int, b: Int, arr: inout [Int]) {
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
}
func selectionSort(arr: [Int]) {
var arr = arr
var minIndex = 0
for i in 0..<arr.count {
minIndex = i
for j in i+1..<arr.count {
if arr[j] < arr[minIndex] { minIndex = j }
}
if i != minIndex {
swap(a: i, b: minIndex, arr: &arr)
}
}
}
Swift
복사
⓵첫 원소부터 마지막 원소까지 하나씩 기준 원소로 잡고 ⓶기준 원소 다음 원소들 확인하면서 기준 원소보다 작으면 가장 작은 원소로 설정합니다. ⓷다음 원소들 확인 끝나면 기준 원소보다 작은 값이 있는지 확인하고 ⓸있다면 원소를 교환합니다.
for i in 0..<arr.count {
minIndex = i // ⓵
for j in i+1..<arr.count {
if arr[j] < arr[minIndex] { minIndex = j } // ⓶
}
if i != minIndex { // ⓷
swap(a: i, b: minIndex, arr: &arr) // ⓸
}
}
Swift
복사
원소 교환을 진행하는 swap 함수는 직접 구현했습니다.
func swap(a: Int, b: Int, arr: inout [Int]) {
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
}
Swift
복사
찾아보니 swapAt(_ i: Self.Index, _ j: Self.Index) 이라는 메소드가 있더라구요. 시간 복잡도도 이라서 굳이 따로 swap 함수를 만들지 않아도 괜찮을 거 같네요. swapAt 를 적용해서 코드를 짜면 이렇게 됩니다.
func selectionSort(arr: [Int]) {
var arr = arr
var minIndex = 0
for i in 0..<arr.count {
minIndex = i
for j in i+1..<arr.count {
if arr[j] < arr[minIndex] { minIndex = j }
}
if i != minIndex {
arr.swapAt(i, minIndex)
}
}
}
Swift
복사
시간 복잡도
위의 코드에서 볼 수 있듯, 선택 정렬의 시간 복잡도는 입니다.
for i in 0..<arr.count { // ⓵
minIndex = i
for j in i+1..<arr.count { // ⓶
if arr[j] < arr[minIndex] { minIndex = j }
}
if i != minIndex {
swap(a: i, b: minIndex, arr: &arr)
}
}
Swift
복사
⓵ 0부터 n까지 원소를 한 개씩 탐색하기 때문에,
⓶ i+1부터 n까지 원소를 한 개씩 탐색하기 때문에,
● 결론적으로, 가 걸리게 됩니다. 좋은 성능의 알고리즘은 아닙니다.
Swift의 sort(), sorted() 가 의 시간복잡도를 가진다는걸 안다면, 굳이 선택 정렬 코드를 작성하지 않고 주어진 메소드를 사용할 것 같네요.
실제로 sort() 보다 성능이 좋지 않은지 확인하기 위해서 실행 시간을 측정을 해봤습니다. 저는 10000부터 1까지 거꾸로 들어있는 배열을 하나 만들었습니다.
var arr: [Int] = []
stride(from: 10000, through: 1, by: -1).forEach {
arr.append($0)
}
Swift
복사
그리고 해당 배열을 선택 정렬과 swift에 있는 sort()로 정렬을 진행했습니다.
•
선택 정렬
•
sort()
시간 차이가 어마어마 하군요.. 그냥 주는거 쓰겠습니다.^^
+⍺
혹시나 완전 거꾸로 된 배열이기 때문에 성능이 구렸던 게 아닐까 싶어서 완전히 정렬이 되어있는 배열을 넣어보았습니다. 어떤 상황에 있던지 for문을 현재 기준 원소로부터 끝까지 돌리기 때문에 비슷할 거라고 예상하긴 했습니다.
네, 그렇습니다. 정직하네요.. 관련 코드는 깃허브에 올려뒀습니다.
관련 코드는 깃허브에 올려뒀습니다.