1. 고급 정렬(Advanced Sort)
Advanced Sort
•
기본 정렬 : 선택 정렬, 삽입 정렬, 버블 정렬
•
기본 정렬 시간복잡도 : O(n^2)
•
O(n log n)만에 정렬할 수 있는 알고리즘 : 합병 정렬, 퀵 정렬, 힙 정렬
2. 로그의 개념과 그 효율성
Tip
•
로그의 정의 : 지수함수의 역함수, logx(y) = z ----> x ^ z = y
•
즉, x를 몇 번 곱해야 y가 되는가?
•
컴퓨터공학에서 log를 사용하는 경우, 그 밑이 2 이므로 보통 밑을 생략합니다.
•
log가 있는 경우, 시간 복잡도를 많이 줄일 수 있으므로 효율적인 알고리즘이라고 할 수 있습니다.
3. 합병 정렬(Merge Sort)
Merge Sort
•
재귀호출을 이용하여 구현할 수 있습니다.
•
배열을 절반으로 나누어 각가을 정렬한 후 합치는 형태입니다.
•
시간 복잡도 : O(n log n)
4. 합병 정렬의 구현
•
재귀함수이므로, 재귀함수 디자인 규칙을 따릅니다.
•
mergeSort(array, start, end) // array를 start번 째 값 부터 end번 째 값 까지 합병 정렬하는 함수
var array: [Int] = [-1, 2, 5, 10, 8]
var tempArray: [Int] = Array(repeating: 0, count: array.count + 10)
func mergeing(_ s1: Int, _ s2: Int, _ e1: Int, _ e2: Int) -> Void {
var p: Int = s1, q: Int = s2, tempIndex: Int = 0
while p <= e1 && q <= e2 {
if array[p] < array[q] {
tempArray[tempIndex] = array[p]
tempIndex += 1
p += 1
} else {
tempArray[tempIndex] = array[q]
tempIndex += 1
q += 1
}
}
if p > e1 {
for i in stride(from: q, through: e2, by: 1) {
tempArray[tempIndex] = array[i]
tempIndex += 1
}
} else {
for i in stride(from: p, through: e1, by: 1) {
tempArray[tempIndex] = array[i]
tempIndex += 1
}
}
for i in stride(from: s1, through: e2, by: 1) {
array[i] = tempArray[i - s1]
}
}
func mergeSort(_ start: Int, _ end: Int) -> Void {
//array의 start 부터 end까지 합병정렬 하는 함수
if start >= end {
return
}
let mid: Int = (start + end) / 2
mergeSort(start, mid)
mergeSort(mid + 1, end)
merging(start, mid, mid + 1, end)
}
Swift
복사
5. 퀵 정렬(Quick Sort)
Quick Sort
1.
재귀호출을 이용하여 구현할 수 있습니다.
2.
원소를 하나 정하여(pivot), 해당 원소보다 작은 수, 큰 수로 배열을 나누게 됩니다.
3.
시간 복잡도 : pivot이 원소를 절반으로 나눈다고 가정했을 때, 평균적으로 O(n log n)이고, 원소가 이미 정렬되어 있는 경우(최악의 경우) O(n^2)
6. 퀵 정렬의 구현
•
재귀함수이므로, 재귀함수 디자인 규칙을 따릅니다.
•
quickSort(array, start, end) // array를 start번 째 값 부터 end번 째 값 까지 퀵 정렬하는 함수
func getLeft(_ array: [Int], _ start: Int, _ end: Int, _ pivot: Int, _ left: inout [Int]) -> Int {
var index: Int = 0
for i in start...end {
if array[i] <= pivot {
left[index] = array[i]
index += 1
}
}
return index
}
func getRight(_ array: [Int], _ start: Int, _ end: Int, _ pivot: Int, _ right: inout [Int]) -> Int {
var index: Int = 0
for i in start...end {
if array[i] > pivot {
right[index] = array[i]
index += 1
}
}
return index
}
func quickSort(_ array: inout [Int], _ left: inout [Int], _ right: inout [Int], _ start: Int, _ end: Int) {
//array의 start 번 째 값 부터 end 번 째 값 까지 퀵 정렬 하는 함수
if start >= end {
return
}
let pivot: Int = array[start]
let leftCount: Int = getLeft(array, start + 1, end, pivot, &left)
let rightCount: Int = getRight(array, start + 1, end, pivot, &right)
for i in 0..<leftCount {
array[start + i] = left[i]
}
array[start + leftCount] = pivot
for i in 0..<rightCount {
array[start + leftCount + 1 + i] = right[i]
}
quickSort(&array, &left, &right, start, start + leftCount - 1)
quickSort(&array, &left, &right, start + leftCount + 1, end)
}
Swift
복사
7. 대표 정렬 알고리즘 시간 복잡도 비교(Time Complexity Of Sort Algorithm)
선택 정렬(Selection) | 삽입 정렬(Insertion) | 버블 정렬(Bubble) | 합병 정렬(Merge) | 퀵 정렬(Quick) | |
평균 시간복잡도 | - | - | - | - | O(N log N) |
최악의 경우 | O(N^2) | O(N^2) | O(N^2) | O(N log N) | O(N^2) |