Lecture 5: Linear Sorting
Lecture 5: Linear Sorting
1. Review 복습
Comparison search lower bound: any decision tree with n nodes has height ≥ ⌈log₂(n+1)⌉−1
비교 기반 탐색 알고리즘은 최소한 ⌈log₂(n+1)⌉−1 높이의 결정 트리를 가진다.
즉, 어떤 비교 기반 탐색을 사용하더라도 최소 log(n) 만큼은 비교해야 한다
Can do faster using random access indexing: an operation with linear branching factor!"
하지만 비교 기반이 아닌 방법, 예를 들어 랜덤 액세스 인덱싱을 사용하면,
브랜칭 팩터가 선형(즉, 한 번에 많은 선택지 접근 가능)이라서 더 빠르게 탐색할 수 있다
* random access indexing: 배열의 인덱스에 접근하듯 원하는 위치에 한 번에 접근할 수 있는 것 O(1)
연결 리스트(linked list)처럼 순차적으로 따라가야 하는 구조는 random access가 불가능.
* 브랜칭 팩터 (branching factor): represents the average number of children. 한 노드에서 갈 수 있는 선택지(자식 노드) 수
트리: 각 노드에서 몇 개 안 되는 자식만 접근 가능 → 브랜칭 팩터 작음
배열: 모든 인덱스가 자식 노드인 것처럼 바로 접근 가능 → 브랜칭 팩터가 선형(=많음)
Direct access array is fast, but may use a lot of space (Θ(u))
키를 직접 배열 인덱스에 접근하는 방식(예: Direct Address Table)은 빠르기는 하지만,
키 공간 u를 미리 확보해 놔야 하는데 이 공간이 너무 커서 메모리 사용량도 Θ(u) 만큼 되어 매우 비효율적으로 된다
예) 데이터는 단 3개만 있음: 키가 각각 5, 101, 9999999
그러나 키 범위는 0부터 9,999,999까지 가능 (u = 10^7)
이걸 직접 주소 테이블로 만들면?
u = 10_000_000 # 전체 키 공간
T = [None] * u # 1천만 개 공간을 할당!
T[5] = "apple"
T[101] = "banana"
T[9999999] = "cherry"
메모리 사용량
- 배열의 크기: u = 10,000,000
- 각 요소가 8바이트 (64비트 시스템에서 포인터 크기)라고 하면:
→ 10,000,000 × 8바이트 = 80MB - 저장한 데이터는 고작 3개뿐인데도 80MB나 차지!
Solve space problem by mapping (hashing) key space u down to m = Θ(n)"
그래서 이 공간 낭비 문제를 해결하기 위해,
키 공간 u를 더 작은 공간 m = Θ(n) 으로 매핑하는 해시(Hashing) 기법을 사용한다
필요할 만큼의 공간만 사용하면서 빠르게 접근 가능!
Hash tables give expected O(1) time operations, amortized if dynamic"
해시 테이블은 평균적으로 (기댓값 기준) O(1) 시간에 연산을 처리할 수 있고,
해시 테이블의 크기 조절이 필요할 경우에도 분할 상환 O(1) 시간으로 처리할 수 있다
Expectation input-independent: choose hash function randomly from universal hash family
이 기대 성능은 입력과 무관하게 보장된다
왜냐하면 해시 함수를 매번 무작위로 유니버설 해시 패밀리에서 선택하기 때문
입력에 따라 해시가 나빠질 가능성이 줄어든다
Data structure overview!
Last time we achieved faster find. Can we also achieve faster sort?
지난 시간엔 해시를 사용해서 탐색을 더 빠르게 하는 방법을 알아 봤는데
정렬도 더 빠르게 할 수 있는 방법이 있을까요?
2. Comparison Sort Lower Bound
Comparison model implies that algorithm decision tree is binary (constant branching factor)
비교 기반 정렬 모델은 각 단계에서 두 항목을 비교하므로,
알고리즘의 결정 트리는 2갈래(binary)이며
각 노드가 항상 두 선택지(작다/크다)로 갈라지는 구조이다.
Requires # leaves L ≥ # possible outputs
가능한 아웃풋 수보다 같거나 더 많은 리프가 필요하다
이 트리의 리프(leaf)는 정렬 결과를 의미하고, 가능한 정렬 결과 수만큼 리프가 필요하다
Tree height lower bounded by Ω(log L), so worst-case running time is Ω(log L)
트리의 높이는 최소한 log(L) 이상이어야 하므로, 최악의 경우 비교 횟수는 Ω(log L) 만큼 필요해진다
리프 개수가 많을수록 트리가 깊어짐 → 비교도 많아짐
예1)
총 리프(결과): 6개 = 3! → 가능한 정렬 결과 모두 포함
- 이 트리의 깊이 = (최악의 경우) 비교 횟수
- 즉, 최악의 경우 3번 비교해야 정렬 순서를 결정할 수 있음
- 가능한 정렬 결과가 많아질수록 (n!개) → 트리도 커지고 깊어짐 → 최소 Ω(log(n!)) = Ω(n log n)의 비교가 필요함
예2) A, B, C, D (4개 원소)
가능한 정렬 결과: 총 경우의 수 = 4! = 24개 → 트리에 24개의 리프
트리 높이는 최소 얼마? 이진 트리에서 리프가 24개 이상이면, 높이는 최소:
따라서 비교 기반 정렬 알고리즘은 최악의 경우 최소 5번의 비교를 해야 어떤 정렬 결과인지 결정할 수 있음.
예시) 원소수에 따른 결과수와 최소 트리 높이
| n (원소수) | n! (정렬 결과 수) | 최소트리 높이 (Ω(log n!)) |
| 4 | 24 | 5 |
| 8 | 40320 | 16 |
| 10 | 3628800 | 22 |
비교 기반 정렬은 최악의 경우 반드시 이만큼 비교해야 하므로, Ω(n log n) 보다 빠를 수 없다
To sort array of n elements, # outputs is n! permutations"
n개의 서로 다른 원소를 정렬하는 방법은 n! 가지이므로,
결정 트리에는 최소한 n!개의 리프가 있어야 한다
Thus height lower bounded by
- 비교 기반 정렬 알고리즘은 입력을 비교하여 정렬함
- 가능한 모든 입력 순열의 수 = n!
- 결정 트리(decision tree)의 최소 높이 h ≥ log₂(n!) (왜냐면 최소한 n!개의 리프 노드가 필요하니까)
- 따라서 최악의 경우 수행 시간도 Ω(log(n!))
의 하한 구하기
비교 기반 정렬 알고리즘은 최악의 경우에도 Ω(n log n)보다 빠를 수 없다는 것을 증명하기 위해 log(n!)의 하한을 구한다
n!은 다음보다 크다는 것을 활용합니다:
왜냐하면:
n! = 1 × 2 × 3 × ... × n
그 중에서 n/2부터 n까지는 n/2개가 있고,
그 값은 각각 n/2 이상이므로:
로그 취하기
상수들을 다 떼고 나면 Θ(n log n) 이 된다
그래서 n!은 Ω(n log n)보다 빠른 순 없다
So merge sort is optimal in comparison model
머지 소트(Merge Sort)는 항상 O(n log n) 시간이 걸리므로, 이 이론적 하한과 일치한다
비교 기반 모델에서 최적 알고리즘이다
Can we exploit a direct access array to sort faster?"
그럼 비교가 아니라 직접 접근 가능한 배열 구조를 이용하면 더 빠르게 정렬할 수 있지 않을까?
3. Direct Access Array Sort
Example: [5, 2, 7, 0, 4]
예시로 정렬할 숫자 리스트
Suppose all keys are unique non-negative integers in range {0, . . . , u − 1}, so n ≤ u
모든 키가 0 이상 u−1 이하의 고유한 정수라고 가정한다.
따라서 전체 개수 n은 u보다 작거나 같다. (n ≤ u)
Insert each item into a direct access array with size u in Θ(n)
키를 인덱스로 그대로 사용해서 크기 u의 배열에 값을 넣는다
각 값은 자기 자리로 바로 들어가므로 Θ(n) 시간에 끝난다
예시) 아이템들이 [5, 2, 7, 0, 4] 이므로, 최대값 7에 맞춰
Direct Access Array의 크기를 u = 8 (index 0 ~7까지 필요) 만들어준다
크기 8개의 초기 배열을 만들어 보자
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Value | – | – | – | – | – | – | – | – |
이제, [5, 2, 7, 0, 4] 값을 배열에 넣어보자. 각 값은 같은 번호의 인덱스에 넣는다
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Value | 0 | – | 2 | – | 4 | 5 | – | 7 |
Return items in order they appear in direct access array in Θ(u)
이제 배열의 0부터 u−1까지 순서대로 스캔하면 정렬된 결과가 나옵니다.
이 작업은 Θ(u) 시간이 걸린다.
실제 아이템이 있는지 없는지를 확인하면서 스캔하므로, D[i]가 비어 있어도 무조건 지나가야 한다.
Running time is Θ(u), which is Θ(n) if u = Θ(n). Yay!
전체 시간복잡도는 Θ(n + u) ≈ Θ(u) 이지만 u가 n과 비슷한 크기면 Θ(n)으로 정렬 성공!
매우 빠르고 단순한 정렬 방식 (조건만 맞으면!)
What if keys are in larger range, like u = Ω(n²) < n²?
하지만 키의 범위가 너무 커지면 (예를 들어 u = Ω(n²) 인 경우)
direct access 배열을 만들기엔 공간이 너무 커서 비효율적이 된다
Direct Access Array 문제점 발견 예시)
- 정렬할 원소 개수가 5개인 경우 n
- 정렬할 데이터 [1003, 7002, 12345, 9999, 8888]
- 즉, 각 값은 1000 이상 13000 이하의 큰 값들
Direct Access Array (DAA)는 각 값을 인덱스로 직접 쓰는 방식이라
배열의 인덱스가 키 값 그 자체: A[1003] = 1003, A[7002] = 7002, … A[12345] = 12345를 담으려면
배열의 크기가 최소 12346 이상이어야 함 (최댓값 + 1)
여기서 문제점이 보인다
- 실제 데이터 개수는 5개 밖에 없는데
- 배열 크기는 12346개 !! (공간 복잡도 Θ(u) = Θ(12346))
→ 메모리 낭비가 너무 심함
이런 공간을 낭비 하지 않을 방법이 없을까?
Idea! Represent each key k by tuple (a, b) where k = an + b and 0 ≤ b < n
각 숫자 키 k를 (a, b)라는 두 숫자의 쌍(tuple)을 k = an + b and 0 ≤ b < n 형태로 바꿔서
메모리 낭비를 줄이는 방식이 있다
* tuple: 쌍(pair),두 개의 값을 묶는 것
* tuple (a, b): 두 값을 하나의 단위로 묶음
Specifically a = ⌊k/n⌋ < n and b = (k mod n) (just a 2-digit base-n number!)
구체적으로는 a와 b 둘 다 n보다 작기 때문에, n × n개의 가능한 쌍만 고려하면 돼요.
즉, 배열의 크기를 u 대신 n²로 제한할 수 있음
This is a built-in Python operation (a, b) = divmod(k, n)
파이썬에서는 divmod(k, n)을 쓰면 (k // n, k % n)을 동시에 계산해준다.
이걸 사용해서 a와 b를 쉽게 얻을 수 있다.
Example:
[17, 3, 24, 22, 12]
⇒ [(3,2), (0,3), (4,4), (4,2), (2,2)]
⇒ [32, 03, 44, 42, 22](n=5)
How can we sort tuples?
이제 남은 문제는 이런 (a, b) 튜플들을 어떻게 빠르게 정렬할 수 있을까?
다음 예시 데이터를 튜플로 정렬해보자. n = 5
1. 튜플로 바꾸기
| 원래 값 k | a 값 계산 (k / n) | a = [k/n] | b 값 계산 (k mod n) | b (k mod n) | 튜플 (a, b) |
| 17 | 17 / 5= 3 | 3 | 17 % 5 = 2 | 2 | (3, 2) |
| 3 | 3 / 5= 0 | 0 | 3 % 5 = 3 | 3 | (0, 3) |
| 24 | 24 / 5= 4 | 4 | 24 % 5 = 4 | 4 | (4, 4) |
| 22 | 22 / 5= 4 | 4 | 22 % 5 = 2 | 2 | (4, 2) |
| 12 | 12 / 5= 2 | 2 | 12 % 5 = 2 | 2 | (2, 2) |
이렇게 각 원소를 divmod(k, 5)로 나누면
- 17 → (3,2) → 32
- 3 → (0,3) → 03
- 24 → (4,4) → 44
- 22 → (4,2) → 42
- 12 → (2,2) → 22
이런 식으로 2자리 base-n 형식으로 표현된다
2. 튜플로 정렬하기
튜플은 (a 우선 정렬, 그 다음 b) 기준으로 정렬
- (0, 3)
- (2, 2)
- (3, 2)
- (4, 2)
- (4, 4)
3. 정렬된 튜플 → 원래 값으로 복원
k=a⋅n+b
(a, b)계산 a⋅n+ba \cdot n + b원래 값
| 정렬된 튜플 | 계산 a⋅n + b | 원래 값 |
| (0, 3) | 0⋅5 + 3 = 3 | 3 |
| (2, 2) | 2⋅5 + 2 = 12 | 12 |
| (3, 2) | 3⋅5 + 2 = 17 | 17 |
| (4, 2) | 4⋅5 + 2 = 22 | 22 |
| (4, 4) | 4⋅5 + 4 = 24 | 24 |
4. 최종 정렬 결과
[3, 12, 17, 22, 24]
4. Tuple Sort
Item keys are tuples of equal length, i.e. item x.key = (x.k1, x.k2, x.k2, . . .).
아이템들의 키는 모두 같은 길이의 튜플(쌍) 형태이다.
예로 한 자리수 3을 (0,3), 17을 (3,2) 모두 같은 자리 갯수로 맞춤
- 3 → (0,3)
- 17 → (3,2)
Want to sort on all entries lexicographically, so first key k1 is most significant
이 튜플들을 사전식 순서(lexicographic order)로 정렬하고 싶다.
즉, (k1, k2, k3...) 순서대로 비교하면서, 가장 앞의 k1이 가장 중요한 기준이 된다
사전에서 단어 정렬할 때 앞 글자부터 비교하는 방식과 같다
* lexicographically: 사전식 순서로 (lexicographic order)
How to sort? Idea! Use other auxiliary sorting algorithms to separately sort each key
그럼 어떻게 정렬 해야 할까?
보조 정렬 알고리즘(auxiliary sorting algorithms)을 사용해서 튜플의 각 요소(각 열)를 따로 정렬한다
(Like sorting rows in a spreadsheet by multiple columns)
예를 들어, 엑셀에서 표를 정렬할 때 여러 열을 기준으로 정렬하는 것과 같다
먼저 ‘성’을 기준으로, 그 다음 ‘이름’을 기준으로 정렬하는 것처럼
What order to sort them in? Least significant to most significant!
그러면 어떤 순서로 열을 정렬해야 할까?
가장 중요하지 않은 값(가장 뒤에 있는 열)부터, 가장 중요한 값(가장 앞에 있는 열) 순으로 정렬한다
Exercise: [32, 03, 44, 42, 22] ⇒ [42, 22, 32, 03, 44] ⇒ [03, 22, 32, 42, 44]
우리는 앞 서 데이터 [32, 03, 44, 42, 22] 를 튜플로 만들어 보았었다
원래 숫자 튜플 표현 (k₁, k₂) 1단계: k₂ 기준 정렬 한 후 2단계: k₁ 기준 정렬 (최종 결과)
| 원래 숫자 | 튜플 표현 (k1, k2) | 1단계: 두번 째 자리 정렬(k2) 기준 정렬 | 2단계: 그 다음 첫 번째 자리(k1) 기준 정렬 (최종 결과) |
| 32 | (3, 2) | (4, 2) → 42 | (0, 3) → 03 |
| 03 | (0, 3) | (2, 2) → 22 | (2, 2) → 22 |
| 44 | (4, 4) | (3, 2) → 32 | (3, 2) → 32 |
| 42 | (4, 2) | (0, 3) → 03 | (4, 2) → 42 |
| 22 | (2, 2) | (4, 4) → 44 | (4, 4) → 44 |
- 먼저 두 번째 자리(k2) 기준으로 정렬:
[(4,2), (2,2), (3,2), (0,3), (4,4)] ⇒ [42, 22, 32, 03, 44] - 그 다음 첫 번째 자리(k1) 기준으로 정렬:
[(0,3), (2,2), (3,2), (4,2), (4,4)] ⇒ [03, 22, 32, 42, 44]
이렇게 두 단계로 안정 정렬을 사용하면, 전체 튜플들이 사전순으로 잘 정렬된다.
Idea! Use tuple sort with auxiliary direct access array sort to sort tuples (a, b).
튜플 (a, b)를 정렬하기 위해 보조 정렬 방법으로
direct access array sort(직접 접근 배열 정렬)을 사용하는 튜플 정렬 방식을 써보면 어떨까?
즉, (a, b)를 두 번 정렬해서 전체 순서를 맞추자는 전략이다.
* auxiliary direct access array sort:
(메인 정렬을 돕기 위한) 보조 수단으로 사용하는 직접 접근 배열 정렬 방법
튜플의 일부(a 또는 b)만 정렬
Problem! Many integers could have the same a or b value, even if input keys distinct
문제는 입력 값들이 전부 다르더라도, (a, b) 형태로 표현하면 여러 숫자들이 같은 a 값이나 같은 b 값을 가질 수 있다
예를 들면
| k | a = k // 5 | b = k % 5 | (a, b) |
| 7 | 1 | 2 | (1, 2) |
| 12 | 2 | 2 | (2, 2) |
| 17 | 3 | 2 | (3, 2) |
| 22 | 4 | 2 | (4, 2) |
| 27 | 5 | 2 | (5, 2) |
n = 5, 5개의 아이템
Need sort allowing repeated keys which preserves input order
그래서 필요한 건, 같은 키 값들이 있더라도 원래 입력 순서를 그대로 유지해주는 정렬 방법이다.
Want sort to be stable: repeated keys appear in output in same order as input
우리가 원하는 정렬은 안정 정렬이다
즉, 동일한 키 값을 가진 항목들은 출력에서도 입력 순서 그대로 나와야 한다
안정 정렬에 대해 살펴보자
예를 들면
정렬할 데이터 [
(3, "apple"),
(1, "banana"),
(2, "cherry"),
(1, "grape")]
인 경우
첫 번째 숫자를 기준으로 보면 1, 1, 2, 3 순으로 정렬한다
하지만 중요한 건 같은 숫자 1을 가진 두 항목의 순서이다
입력 순서에서 (1, "banana")가 먼저, 그다음이 (1, "grape")였으니
출력에서도 다음과 같이 이 순서가 유지되어야 한다.
[(1, "banana"), (1, "grape"), (2, "cherry"), (3, "apple")]
하지만 정렬 알고리즘이 안정적이지 않다면
같은 '1' 중에서 banana가 아닌 grape가 먼저 와버릴 수 있다.
[(1, "date"), (1, "banana"), (2, "cherry"), (3, "apple")]
이렇게 되면 첫 번째 아이템은 정렬이 잘 되었으니 뒤의 과일 이름은 알파벳 순으로 정렬이 되지 않아
→ 불안정 정렬! 안정성이 보장 되지 않았다고 본다
Direct access array sort cannot even sort arrays having repeated keys!
여기서 또 하나 알아할 점은 Direct Access Array Sort는 키 값이 반복되는 경우 아예 처리 자체가 안 된다
왜냐하면 배열 안에 인덱스가 같은 두 값을 넣을 수 없기 때문이다.
Can we modify direct access array sort to admit multiple keys in a way that is stable?
Direct Access Array Sort를 변형해서 중복 키들을 처리하고, 안정성까지 보장할 수 있는 방법이 있을까?
같은 인덱스에 여러 값을 넣을 수 있도록 하는 방법이 있을까?
결론부터 말하면
전체 정렬은 Radix Sort로, 각 단계 정렬은 Counting Sort를 사용한다
- Radix Sort: 자리수별로 여러 번 정렬 반복 → 전체 정렬
- Counting Sort: 각 자리수에서 사용하는 안정 정렬 알고리즘
5. Counting Sort
Instead of storing a single item at each array index, store a chain, just like hashing!
배열의 각 인덱스에 아이템 하나만 저장하는게 아니라, 여러 아이템들을 담을 수 있는 체인(chain)을 저장해보자.
이는 해시 테이블에서 충돌을 해결하기 위해 체이닝을 사용하는 방식과 비슷하다
즉, 같은 키 값을 가지는 항목이 여러 개 있어도 전부 담을 수 있도록 만든다
For stability, chain data structure should remember the order in which items were added
그리고 정렬의 안정성을 위해서는, 체인 자료구조는 항목들이 삽입된 순서를 기억해야 한다
Use a sequence data structure which maintains insertion order
따라서 체인으로는 삽입 순서를 유지하는 순차형 자료 구조를 사용해야 한다
예: Python의 list, Java의 LinkedList, C++의 std::vector 등
이 구조들은 순서대로 넣으면, 꺼낼 때도 그 순서가 보장된다
To insert item x, insert last to end of the chain at index x.key
어떤 항목 x를 넣을 때는, x.key 값에 해당하는 인덱스 체인 맨 뒤에 추가한다
index = x.key 인 리스트 위치에 x를 append하는 방식이다
Then to sort, read through all chains in sequence order, returning items one by one
정렬을 마치려면, 모든 인덱스를 0부터 순서대로 보면서, 그 인덱스에 있는 체인을 앞에서부터 하나씩 꺼내기만 하면 된다
그러면 전체 항목들이 키 순으로, 그리고 같은 키일 경우 입력 순서대로 정렬된 상태로 나온다
예시 코드로 살펴보자
def counting_sort(A):
"Sort A assuming items have non-negative keys"
u = 1 + max([x.key for x in A]) # O(n) A 안에서 가장 큰 key 값을 찾는다
D = [[] for i in range(u)] # O(u) 크기 u의 빈 리스트 배열 D를 만든다
for x in A: # O(n) A의 각 아이템 x에 대해, x.key에 해당하는 D의 체인에 추가한다
D[x.key].append(x)
i = 0
for chain in D: # O(u) D 배열의 각 체인(리스트)을 순서대로 돌며, A에 다시 채워 넣는다.
for x in chain:
A[i] = x
i += 1
* D ?
- D는 리스트(list)이다
- D[0], D[1], ..., D[u-1] 각각이 빈 리스트이다
- 즉, D는 리스트들의 리스트, 즉 체인(chain)의 배열(array) 이라고 부른다
실행 도중 D는 다음과 같이 생긴다
D = [
[item(key=0)], # D[0]
[item(key=1)], # D[1]
[item(key=2), item(key=2)] # D[2] ← 여러 개니까 '체인'
]
6. Radix Sort
Idea! If u < n², use tuple sort with auxiliary counting sort to sort tuples (a, b)
아이디어! 만약 키 값의 범위 u가 n²보다 작다면, 키를 (a, b) 형태의 튜플로 표현해서
Counting Sort(보조 정렬)를 이용한 튜플 정렬 방식으로 정렬할 수 있다
Sort least significant key b, then most significant key a
가장 낮은 자릿수인 b부터 정렬하고, 그다음에 가장 높은 자릿수인 a를 정렬한다.
이건 Radix Sort의 기본 전략이다.
Stability ensures previous sorts stay sorted
안정 정렬을 쓰기 때문에, 먼저 정렬한 b의 순서는 그 이후 정렬에서도 유지된다
그래서 나중에 a 를 정렬해도 b를 기준한 정렬 결과도 유지됨!
Running time for this algorithm is O(2n) = O(n). Yay!
(a, b) 두 자리만 정렬하니까, 각 자리마다 O(n) 시간, 전체는 O(2n) = O(n)
즉, 선형 시간에 정렬 가능!
If every key < nᶜ for some positive c = logₙ(u), every key has at most c digits base n
모든 키가 nᶜ보다 작다면, 이진수처럼 n을 베이스로 하는 표현으로 최대 c자리까지 필요하다
여기서 c = logₙ(u)는 키 범위 u를 기준으로 계산된다
- key: 정렬할 숫자 하나
- n: 아이템 수 (데이터 개수)
- c: 자리 수 (base-n에서 key가 몇 자리 수인지)
- u: key가 가질 수 있는 최대값 (key의 범위 upper bound)
- base-n: n진법, key를 n진법으로 표현
만약 u = 1000, n = 10개 이라면 c = log_10(1000) = 3
예시)
만약 아이템이 [1, 2, 12345] 3개 있는 경우 Radix Sort 분석해보자
* 아이템 갯수 n = 3
* 가장 큰 키를 찾는다
max = 12345
* 그럼 전체 key의 범위 u 가 나온다
u = max + 1 = 12346
* 이제 c를 구할 수 있다
이를 계산하면
c = 9 (올림) 가 나온다
base-3으로 바꾸면 최대 9자리 필요하다
* 시간 복잡도를 구해보면
시간복잡도 O(cn) - O(9⋅3)=O(27)
* [1, 2, 12345]를 base 3 (즉, 3진법)으로 9자리 튜플로 표현해보면 다음과 같다
1 -> (0,0,0,0,0,0,0,0,1)
2 -> (0,0,0,0,0,0,0,0,2)
12345 -> (1,2,1,2,2,1,0,2,0)
12345를 3진법 변환을 단계별로 자세히 나타내면
- 12345 ÷ 3 = 4115, 나머지 0 → 맨 끝자리 a_0 = 0
- 4115 ÷ 3 = 1371, 나머지 2 → a_1 = 2
- 1371 ÷ 3 = 457, 나머지 0 → a_2 = 0
- 457 ÷ 3 = 152, 나머지 1 → a_3 = 1
- 152 ÷ 3 = 50, 나머지 2 → a_4 = 2
- 50 ÷ 3 = 16, 나머지 2 → a_5 = 2
- 16 ÷ 3 = 5, 나머지 1 → a_6 = 1
- 5 ÷ 3 = 1, 나머지 2 → a_7 = 2
- 1 ÷ 3 = 0, 나머지 1 → a_8 = 1
* 이 튜플로 Radix Sort 하는 법
- 가장 덜 중요한 자리 a_0 부터 Counting Sort를 돌려 정렬
- 그다음 a_1, a_2, ... a_8까지 순차적으로 정렬
- 각 단계는 Counting Sort로 시간
- 총 9단계 → O(9n)=O(n) 시간 복잡도
* Radix Sort 메모리 구조 예시
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 아이템 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 아이템 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 아이템 12345 | 1 | 2 | 1 | 2 | 2 | 1 | 0 | 2 | 0 |
이 예시의 경우, key 중 하나만 매우 크면, c 값이 커져서 Radix Sort의 효율이 떨어질 수 있다
그래서 Radix Sort는 모든 key가 비슷한 자릿수를 가질 때 가장 효율적이다
A c-digit number can be written as a c-element tuple in O(c) time
이런 숫자는 c자리 튜플 (ex: (a1, a2, ..., ac))로 표현할 수 있고, 이건 O(c) 시간에 가능하다
We sort each of the c base-n digits in O(n) time
각각의 자리(digit)를 Counting Sort로 정렬하는 데 O(n) 시간이 걸린다
c번 반복하면 총 O(cn)이 된다
So tuple sort with auxiliary counting sort runs in O(cn) time in total
따라서 전체 튜플 정렬 알고리즘은총 O(cn) 시간에 수행됩니다.
If c is constant, so each key is ≤ nᶜ, this sort is linear O(n)!
→ 만약 c가 상수라면 (예: 키 범위가 n³ 이하),
전체 정렬 시간은 O(n)으로 선형 시간이 된다!
출처
자료 https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec5/