버블 정렬
버블 정렬은 인접한 값을 비교해서 더 큰 수를 뒤로 보내 정렬하는 알고리즘이다. 원리 자체가 굉장히 간단하기 때문에 구현도 간편하지만, 시간 복잡도가 O(N^2) 이기 때문에 성능은 떨어진다. 시간 복잡도가 O(N^2)인 이유는 배열의 모든 요소를 한번씩 비교하면서 교환까지 이루어지기 때문이다. 버블 정렬을 Swift로 구현하자면 다음과 같다.
func bubbleSort(arr: [Int]) -> [Int] {
var arr = arr
var totalLength = arr.count - 1
while totalLength != 0 {
for i in 0...totalLength {
let nextIndex = i + 1
if nextIndex <= totalLength {
if arr[i] > arr[nextIndex] {
let small = arr[nextIndex]
arr[nextIndex] = arr[i]
arr[i] = small
}
if nextIndex == totalLength {
totalLength -= 1
}
}
}
}
return arr
}
선택 정렬
선택 정렬은 배열의 모든 요소를 비교하면서 가장 작은 수를 가장 앞으로 보내어 정렬하는 알고리즘이다. 버블 정렬과 마찬가지로 배열의 모든 요소를 비교하지만, 교환은 단 한번만 이루어진다. 그래서 버블 정렬보다 우위에 있지만 빅 오 표기법상 상수를 무시하여 같은 O(N^2) 시간 복잡도를 가진다. Swift로 구현하면 다음과 같다.
func selectionSort(arr: [Int]) -> [Int] {
var arr = arr
var startPosition = 0
while startPosition != (arr.count - 1) {
var lowerNumberIndex: Int!
for i in startPosition...(arr.count - 1) {
if i == startPosition {
lowerNumberIndex = i
} else {
if arr[i] < arr[lowerNumberIndex] {
lowerNumberIndex = i
}
if i == (arr.count - 1) {
let temp = arr[startPosition]
arr[startPosition] = arr[lowerNumberIndex]
arr[lowerNumberIndex] = temp
startPosition += 1
}
}
}
}
return arr
}