이전 포스팅에서 살펴본 정렬 알고리즘들은 평균, 최악의 경우 $O(n^2)$의 시간복잡도를 가지게 되었다.
병합 정렬 (Merage Sort)
"병합 정렬"(또는 합병 정렬)은 문제를 분할하고, 문제를 정복하여 합치는 분할정복을 기반으로 한 정렬 알고리즘이다.
정렬 과정
이러한 분할정복은 "하향식"과 "상향식"구현으로 구분할 수 있는데,
병합 정렬에선 하향식 구현방식을 대부분 사용한다.
하향식(TopDown)방식으로 구현한 병합 정렬의 과정은 다음과 같다.
(아래 그림은 정확한 Top-Down 방식은 아니지만, 분할되고 정복되는 순서만 차이 있을 뿐, 방법은 동일하다.)
- 리스트를 절반으로 나누어 두 부분 리스트로 나눈다.
- 이를 부분 리스트의 길이가 1이하가 될 때까지 재귀적으로 위의 과정을 반복한다. (길이가 1인 부분리스트는 정렬되었다고 볼 수 있다.)
- 이후, 정렬된 두 부분리스트를 합칠 때, "임시 저장공간"에 정렬된 결과를 저장한다.
- 이후, 원본 리스트에 정렬 결과를 복사한다.
시간 복잡도 증명
"분할 정복"의 시간복잡도는 최선, 최악, 평균의 경우 모두 $O(n \cdot logn)$을 갖는다.
왜 $O(n \cdot logn)$알아보기 위해, 각 분할 과정과 정복 과정을 따로따로 살펴보자.
분할 과정
입력의 갯수가 $n$이라고 가정해 보자.
각 총 $k$라 가정하고 Depth별로 분할 횟수를 살펴보면, 위에서부터 순차적으로
$1, 2, 4, 8, ..., 2^k$회씩 분할한다.
이때, Depth는 $log(n)$ 이므로 $k = log(n)$이다.
또한, 이때 지수 로그 공식에 따라 $2^{logn} = n$으로 대체가 가능하다.
따라서 최종적으로 $1, 2, 4, 8, ..., n$회씩 분할한다.
이때, 각 분할작업에 들어가는 시간복잡도는 입력에 비례하지 않기에 상수시간이라 볼 수 있다.
즉, $T(n) = c(1 + 2 + 4 + .. + n) = c(2n - 1) = O(n)$이 된다.
정복 과정
각 Depth마다 모든 원소를 비교하면서 병합을 진행한다.
앞서 말했듯, Depth는 총 $log(n)$이며, 각 Depth마다 총 $n$개의 원소를 비교하는 작업을 진행한다.
따라서, $O(n \cdot logn)$이다.
이때, 분할 과정과 정복과정은 독립적으로 수행되기 때문에, 둘의 시간복잡도는 곱이 아닌 합연산이다.
$O(n \cdot logn + n)$이게 되고, 점근적 표기에서 최고차항 외에는 생략하므로,
최종적으로 병합 정렬은 $O(n \cdot logn)$의 시간복잡도를 갖는다.
수식적으로 증명
$T(n)$을 n개의 원소를 분할 정복할 때의 시간복잡도라고 가정해 보자.
이때, 앞서 말했듯 분할 정복 기법이기 때문에 2개의 부분 리스트로 분할하며,
합칠 때는 총 $n$개의 원소를 비교하기 때문에, $n$의 시간복잡도가 든다.
따라서, $T(n) = 2 \cdot T(n/2) + n$ 으로 볼 수 있다.
$T(n) = 2(2 \cdot T(n/4) + n/2) + n = 4 \cdot T(n/4) + 2n$
$T(n) = n \cdot T(1) + n \cdot logn$
$T(1) = 1$이므로, $T(n) = n + n \cdot logn$이 완성된다.
이때, $g(n) = n \cdot logn$이라 가정할 때, $n_0 \geq 10$이고 $c =2$일 때,
$n \geq n_0$인 모든 자연수에 대하여 $g(n) \geq T(n)$을 만족한다.
점근적 상한의 정의에 의해 $T(n) = $O(n \cdot logn)$가 된다.
특징
- 제자리 정렬 X
- 안정 정렬
- 시간복잡도가 $O(n \cdot logn)$
병합 정렬은 앞서 살펴봤다시피, 병합하는 과정에서 새로운 메모리 공간에 병합을 하고, 이를 원본 메모리에 복사한다.
즉, 추가적인 메모리가 필요하기 때문에 제자리 정렬이 아니다.
구현
extension Array where Element: Comparable {
func mergeSort(
sortedBy: (Element, Element) -> Bool = { $0 < $1 }
) -> [Element] {
return mergeSort(self, st: 0, en: self.count, sortedBy: sortedBy)
}
private func mergeSort(
_ array: [Element],
st: Int,
en: Int,
sortedBy: (Element, Element) -> Bool
) -> [Element] {
guard st < en - 1 else { return array }
let mid = (st + en) / 2
var array = array
array = mergeSort(array, st: st, en: mid, sortedBy: sortedBy)
array = mergeSort(array, st: mid, en: en, sortedBy: sortedBy)
return merge(array, st: st, en: en, sortedBy: sortedBy)
}
private func merge(
_ array: [Element],
st: Int,
en: Int,
sortedBy: (Element, Element) -> Bool
) -> [Element] {
var array = array
let mid = (st + en) / 2
var index1 = st
var index2 = mid
var temp = [Element]()
for _ in st..<en {
if index1 == mid {
temp.append(array[index2])
index2 += 1
} else if index2 == en {
temp.append(array[index1])
index1 += 1
} else if sortedBy(array[index1], array[index2]) {
temp.append(array[index1])
index1 += 1
} else {
temp.append(array[index2])
index2 += 1
}
}
for i in 0..<temp.count {
array[i + st] = temp[i]
}
return array
}
}
퀵 정렬
"퀵 정렬"은 제자리 정렬 알고리즘으로,
분할 정복을 기반으로 수행되며 매우 빠른 속도를 자랑한다.
분할 정복을 기반으로 한다는 점에서 병합 정렬과 유사해 보이지만,
퀵정렬은 제자리 정렬 알고리즘이란 차이점이 있다.
이전 포스팅에서 말했지만,
"제자리 정렬"은 추가적인 메모리 공간의 할당을 필요로 하지 않기 때문에,
공간 지역성(Spatical Locality)에 Cache Hit비율이 높아, 좋은 성능을 자랑한다.
정렬 과정
"퀵 정렬"은 분할 정복을 통해 리스트를 정렬한다.
- 리스트에서 하나의 원소를 선택한다. 이 원소를 "피벗"이라 부른다.
- 현재 리스트를 순회하면서, 피벗보다 작은 원소는 피벗 앞으로, 피벗보다 큰 원소는 피벗 뒤로 위치시킨다.
- 위의 과정으로 "피벗의 위치"가 결정 나므로, 피벗을 기준으로 리스트를 둘로 분할하여 위의 과정을 반복한다.
- 해당 과정을 재귀적으로 반복하여, 리스트의 크기가 0 혹은 1이 될 때까지 반복한다.
매 재귀 호출이 이뤄질 때마다, 피벗의 위치가 결정 난다.
즉, 최소한 하나의 원소의 위치가 결정 나게 되기 때문에, 재귀 호출은 반드시 끝난다는 것을 보증할 수 있으며, 최종적으로는 정렬된다는 것을 알 수 있다.
시간 복잡도 증명
퀵소트에서 $n$개의 원소를 정렬한다고 가정해 보자.
선택된 피벗의 위치가 $m$번째 원소라고 가정했을 때, (단, $m$은 n 이하의 자연수)
정렬과정을 수행 후, $m-1$과 $n-m$개의 원소로 분할되어 재귀적으로 반복한다.
이때, 피벗에 대하여 피벗을 비교하는 연산과 Swap 하는 연산이 이루어지는데,
해당 연산을 $C(n)$이라 가정했을 때, $\Theta(n)$이라 할 수 있다.
(둘은 독립적으로 수행되며 모두 n에 비례하기 때문에 가능하다.)
즉, 퀵소트의 시간복잡도는 다음과 같이 표기할 수 있다.
$T(n) = T(m-1) + T(n-m) + \Theta(n)$ $\leq T(m-1) + T(n-m) + c \cdot n$
$c \geq 3$일때 위의 식은 성립한다.
최악의 경우 (Worst Case)
최악의 경우에는 피봇이 맨 앞의 원소 혹은 맨 뒤의 원소를 선택할 경우이다.
해당 경우에는 균등하게 분할되지 않아 $O(n^2)$의 시간복잡도를 갖게 된다.
즉, 위의 식에서 $m = 1$이거나$m = n$인 경우이다.
이때, $T(0) = 0$ 이므로, 다음과 같이 표기할 수 있다.
이때, 이를 반복적으로 해보게 되면,
측 $T(n) \leq c\cdot n^2$가 성립하므로
$T(n) = O(n^2)$이다.
최선의 경우 (Best Case)
최선의 경우에는 피봇이 항상 균등하게 분할하는 경우이기에, 다음과 같은 식이 성립한다.
이때, $n/2$에 대해서 진행해보면 다음과 같다.
이를 좀 더 일반화해보게 되면 다음과 같다.
이를 통해 위의 수식을 일반화하게 되면 다음과 같다.
이때 $k = logn$이므로, 지수 로그 법칙에 의해 $2^k = n$이 성립한다. 따라서 위의 식은 최종적으로 다음과 같이 성립한다.
따라서, 최종적으로 $T(n) = O(n \cdot logn)$이 성립하게 된다.
평균의 경우 (Average Case)
이때, 피봇을 랜덤하게 선택한다고, 가정했을 때, 각 원소들이 피봇이 될 확률을 $\frac{1}{n}$이다.
즉, 기댓값을 적용하여 위의 식은 아래와 같이 정의할 수 있다.
이때, $\sum_{m=1}^{n}T(m-1) = \sum_{m=1}^{n}T(n-m)$이기 때문에 아래와 같이 표현할 수 있다.
이때, 양변에 $n$을 곱해주게 되면 다음과 같은 수식을 얻게 된다.
($n$은 자연수이기 때문에 부등호의 방향은 바뀌지 않는다)
이때 $n = n-1$을 대입해 보게 되면, 다음과 같은 식을 얻게 된다.
이때 (A)-(B)를 하게 되면, 다음과 같은 식을 얻게 된다.
양 변의 항들을 다음게 되면 최종적으로 다음과 같은 식을 얻게 된다.
이때, 항상 $T(n) \geq T(n-1)$이 성립하기 때문에, 다음과 같이 식을 변경할 수 있다.
즉, 최종적으로 다음과 같은 식을 얻게 된다.
이 때, 양 변을 $frac{1}{n(n+1)}$로 나누게 되면 다음과 같은 식을 얻는다.
해당 식에서 $n = n-1$을 대입하게 되면 다음과 같은 식을 얻게 된다.
해당식의 결과를 위의 식의 $\frac{T(n-1)}{n}$ 대입하게 되면 다음과 같은 결과를 갖는다.
위에서 대입하던 과정을 $T(n-2), T(n-3), ... T(1)$까지 반복하게 되면 최종적으로 다음과 같은 식을 얻게 된다.
이를 정리해 보게 되면 다음과 같다.
이때, 다음과 같은 식이 성립한다.
따라서 최종적으로 다음과 같은 식을 도출해낼 수 있다.
이때, 양변을 다시 $n+1$로 곱하게 되면, 다음과 같다.
마지막으로, 빅-오 점근 표기법 공식에 따라 $T(n) = O(n \cdot log_2n)$의 시간복잡도를 갖는다.
특징
퀵정렬은 다음과 같은 성격을 갖는다.
- 최악의 경우 $O(n^2)$, 최선, 평균의 경우는 $O(n \cdot logn)$의 시간복잡도를 갖는다.
- 제자리 정렬이기에 속도적으로 이점이 있다.
- 불안정 정렬에 속한다.
즉, 퀵 정렬에선 피봇을 어떻게 선택하냐가 성능에서 많은 부분을 차지한다.
우선적으로 맨 앞의 원소를 피벗으로 두는 방법도 있고, 랜덤 하게 선택하는 방법도 있다.
또한, 3개의 피벗 후보를 선택해 그중, 중앙값을 선택하는 방법을 사용하기도 한다.
실제로 1대 99 비율로 계속 쪼개지더라고 시간 복잡도를 $O(n \cdot logn)$이다.
구현
// MARK: - QuickSort
extension Array where Element: Comparable {
enum PivotType {
case random
case first
case middle // 랜덤으로 선택된 3개의 값들 중 중앙값
}
func quickSort(
sortedBy: (Element, Element) -> Bool
) -> [Element] {
guard
self.count > 1,
let pivot = self.pivot(.random)
else { return self }
let left = self.filter { sortedBy($0, pivot) }
var right = self.filter { !sortedBy($0, pivot) }
if let firstIndex = right.firstIndex(of: pivot) {
right.remove(at: firstIndex)
}
let sortedLeft = left.quickSort(sortedBy: sortedBy)
let sortedRight = right.quickSort(sortedBy: sortedBy)
return sortedLeft + [pivot] + sortedRight
}
private func pivot(_ type: PivotType) -> Element? {
switch type {
case .first:
return self.first
case .random:
return self.randomElement()
case .middle:
if let randoms = self.randomElements(count: 3) {
return randoms.sorted()[1]
} else {
return self.first
}
}
}
private func randomElements(count: Int) -> [Element]? {
guard self.count >= count else { return nil }
var flags = Array<Bool>(repeating: false, count: self.count)
var numbers = [Element]()
while numbers.count != count {
let randomIndex = Int.random(in: 0..<self.count)
if !flags[randomIndex] {
flags[randomIndex] = true
numbers.append(self[randomIndex])
}
}
return numbers
}
}
기수 정렬
"기수 정렬"은 안정정렬로,
직접 수들을 비교하는 것이 아닌, 자릿수를 기준으로 정렬하는 알고리즘이다.
우선 정렬 로직은 다음과 같다.
- 1의 자릿수부터 시작해 각 자릿수에 숫자에 해당하는 Bucket에 숫자를 넣는다.
- 이후, Bucket에서 순차적으로 뺸 다면, 1의 자릿수의 정렬이 완료된다.
- 해당 과정을 10의 자리, 100의 자리 가장 높은 차수까지 진행한다.
실행 과정
다음과 같은 배열이 있다고 가정해 보자.
앞서, 자릿수를 기준으로 정렬한다 했기에 총 0~9까지 10개의 bucket이 필요하다.
우선 1의 자릿수별로 다음과 같이 buket에 담는다.
이때, Bucket에 담기는 숫자는 순서대로 진행한다. 따라서, 안정 정렬이다.
이제, 이를 순서대로 Bucket에서 빼내면서 1의 자릿수 정렬을 마친다.
다음으로 10 자릿수 정렬을 시작한다.
이후 마찬가지로, Bucket에서 빼내면서 10의 자릿수 정렬을 마친다.
마지막으로 100의 자릿수를 기준으로 정렬을 시작한다.
위와 같은 과정을 진행하게 되면 정렬이 완료되게 된다.
특징
우선 가장 큰 특징은 시간복잡도가 $O(w\cdot n)$이라는 것이다.
(n개의 숫자 중 가장 높은 차수를 w라고 가정)
즉, $w$가 작다면, 시간복잡도 측면에선 어떠한 알고리즘보다 빠르다.
또한, 제자리 정렬이다.
하지만, 2141125....909등과 같이 차수가 매우 높은 숫자가 있다면, 해당 알고리즘의 시간복잡도는 $O(n^2)$에 수렴할 수도 있다.
따라서, 적절한 도메인에서는 빠른 수행시간을 자랑한다.
또한, 앞서 살펴봤듯 버킷이라는 추가적인 공간이 필요하게 된다.
구현
// MARK: - Radix Sort
extension Array where Element: BinaryInteger {
func radixSort(
sortedByAscending: Bool = true
) -> [Element] {
let radix = 10
var done = false
var index: Element = 1
var returnArray = self
while !done {
done = true
var buckets: [[Element]] = .init(repeating: [], count: radix)
returnArray.forEach {
let remainPart = $0 / index
let digit = remainPart % Element(radix)
let digitIndex = Int(digit)
buckets[digitIndex].append($0)
remainPart > 0 ? done = false : ()
}
sortedByAscending ? (returnArray = buckets.flatMap { $0 }) : (returnArray = buckets.reversed().flatMap { $0 })
index *= Element(radix)
}
return returnArray
}
}
References
위키백과
'CS > Algorithm' 카테고리의 다른 글
| [Algorithm] 그래프 탐색 알고리즘 - BFS & DFS (1) | 2024.08.16 |
|---|---|
| [Algorithm] 정렬 알고리즘(1) - 버블정렬, 선택정렬, 삽입정렬 (0) | 2024.07.10 |
| [Algorithm] 알고리즘이란? (1) | 2024.07.08 |
| [PS] BOJ 2457 (공주님의 정원) (0) | 2024.06.23 |
| [PS] BOJ 1539(이진 검색 트리) (0) | 2024.06.18 |