Lower bound proof (in the worst-case) for sorting by comparisons
비교 기반 정렬의 최악 하한 증명
can be represented as a decision tree 결정 트리(Decision Tree) 모델
예를 들어, 세 개의 키 a,b,c를 정렬하는 다음과 같은 알고리즘을 생각해 보자.
리프 노드(leaf nodes) 는 가능한 해답(정렬된 순서)을 나타내며, 총 n! 개가 있음.
n개의 키로 만들 수 있는 모든 순열 수와 일치.
※ 모든 키 x1,x2,…,xn는 서로 다르다고 가정.
결정 트리 모델(Decision Tree Model)
키 비교 기반 정렬 알고리즘은 항상 “비교 → 분기” 구조의 이진 결정 트리로 표현할 수 있다.
예를 들어, 세 키 a,b,c를 정렬하는 경우, 내부 노드에서는 a<b, b<c 등의 비교를 수행하고, 그 결과(“Yes”/“No”)에 따라 왼쪽·오른쪽 가지로 내려간다.
리프 노드(leaf nodes)는 모든 비교가 끝난 뒤 얻어지는 정렬된 순서이며, 가능한 순열 수 n!개와 같다.
높이(lower bound) 계산
높이가 k인 이진 트리는 최대 2^k개의 리프를 가질 수 있다.
따라서 n! ≤ 2k ⟹ k ≥ log2(n!)이고, k는 정수이므로, 결정 트리의 높이는 최소 ⌈log2(n!)⌉다.
비교 횟수와 시간 복잡도
정렬 알고리즘이 수행하는 비교 횟수는 결정 트리의 높이에 해당한다.
따라서 어떠한 키 비교 기반 정렬도 최악의 경우 Ω(log2(n!))번의 비교가 필요하며, Stirling 근사 등을 이용해 log2(n!)=Ω(nlogn)임을 보일 수 있다.
결론: 비교 기반 정렬의 최저 한계(lower bound) 는 Ω(nlogn)이다.
Bucket Sort vs. Radix Sort
Bucket Sort
Radix Sort
based on range
based on the base of numbers
Sort keys in buckets
Not sort keys in buckets
Two passes needed - 1st pass for inserting into buckets - 2nd pass for sorting keys in buckets
두 번의 패스가 필요 - 첫 번째 패스: 키를 버킷에 분배 - 두 번째 패스: 각 버킷 안의 키를 정렬
Multiple passes needed - # passes = Number of digits
여러 번의 패스가 필요 - 패스 횟수 = 자릿수(digits)의 개수
Review: Radix Sort (기수정렬)
Assumption 가정
The keys are all non-negative integers in a fixed base (radix), e.g., 10. 비음수 정수(동일 자릿수)
All keys have the same number of digits. 고정 진법
Sort by distribution: general algo.
Distributes keys into distinct piles (buckets) based on the leftmost digit
Each pile can then be distributed into distinct piles based on the 2nd digit
and so on ...
키를 가장 왼쪽(최상위) 자리수를 기준으로 서로 다른 더미(버킷)들로 분배한다.
각 더미 안의 키들을 두 번째 자리수를 기준으로 다시 서로 다른 더미들로 분배한다.
이 과정을 마지막(최하위) 자리수까지 반복한다.
마지막으로, 모든 더미를 원래 순서대로 차례로 꺼내 붙여 합치면 정렬이 완성된다.
MSD vs LSD
MSD: Most-Sifnificant-Digit from left to right
최상위 digit부터 → 재귀적으로 각 버킷 탐색
LSD: Least-Significant-Digit from right to left
최하위 digit부터 → 반복적으로 한 번에 r개 버킷
각 키 ki가 가질 수 있는 값들의 개수를 기수(radix)라고 부름.
즉, radix란 “한 자리(또는 한 단계)에서 키가 취할 수 있는 서로 다른 값의 수”를 의미.
예를 들어, 10진수 키를 다룬다면 radix = 10이고, 이진수 키를 다룬다면 radix = 2가 됨.
시간 복잡도
If we have n keys with d digits and use r buckets for radix sort, d번 패스 × Θ(r + n) = Θ(d(r+n))
Time complexity for each pass: Θ(r + n)
각 패스의 시간 복잡도는 r개의 각 버킷의 초기화에 필요한 시간 Θ(r)과 n개의 키를 분배하는데 필요한 시간 Θ(n)을 합한 Θ(r + n)
# of passes: d
Radix Sort Example (LSD)
입력: (34,18,55,08,35,07,86,27,91,40)
1차(1의 자리): bucket0→40, …, bucket8→18,08, …
2차(10의 자리): bucket0→07,08, … → 최종 [07,08,18,27,34,35,40,55,86,91]
Searching: findMinMax problem
문제: n개 키에서 최댓값·최솟값을 동시에 구하기
단순 방법: Max 찾고 Min 찾기 → (n-1) + (n-1) = 2n−2 비교
divide-and-conquer 분할정복:
반씩 나누어 각 부분에서 (min, max) 구함 → 두 부분 간 비교 2회 추가
Psudo-code
Input: array, left, right
Output: (MIN, MAX)
procedure MaxMin(A, i, j)
if i = j then return (A[i], A[i]) # No comparisons needed
else if j − i = 1 then if A[i] < A[j] then return (A[i], A[j])
else return (A[j], A[i]) # One comparison needed
else
mid ← ⌊(i + j) / 2⌋ # Divide into n/2-size subproblems
(minL, maxL) ← MaxMin(A, i, mid)
(minR, maxR) ← MaxMin(A, mid + 1, j)
return (min(minL, minR), max(maxL, maxR)) # Two comparisons needed
Time complexity ( # of comparisons)
If n=1, T(1)=0, (no comparisons needed)
n=1일 때, 즉 i=j일 때, 바로 a[i]값 반환하므로, 비교 X
If n-2, T(2)=1, (one comparison for two keys)
n=2일 때, 두 원소를 한 번 비교하여 큰 원소를 max로 반환하고 작은 원소를 min으로 반환
If n>2, T(n) = 2T(n/2) + 2
인덱스 mid에 의해 배열을 대략 n/2씩 두 부분으로 나누게 되고, 각 부분 배열에서 수행하는 비교 횟수는 T(n/2)
각 부분 배열에서 최대값을 구한 후, 원래 문제의 최대 최소 값을 구하기 위해서는 두 번의 비교를 추가로 함.
Thus, T(n) = 3n/2 - 2 comparisons
Searching: find2ndMax problem
Naïve solution: Max 두 번 호출 → n−1+n−2비교
For x1,x2,x3,x4,x5, 4 comparisons to find MAX and further make 3 comparisons to find 2ndMAX
Total 7 comparisons
Better approach
After 1st comprison, winners are x2,x4,x6,x7
After 2nd comparison, winners are x4, x6
After 3rd comparison, winners are x6 (MAX)
2ndMAX = max(x4,x7,x5) # losers against x6
Time complexity:
findMAX: n-1 comparisons
The number of losers to x6: height of the tree (log2n)
max(x4,x7,x5): log2n -1 comparisons
Thus, n-1 + log2n -1 = n+ log2n -2
이 방식은 “토너먼트”를 통해 최대값을 찾고, 그 과정에서 최대값과 겨뤘던(비겼던 게 아니라 패배한) 후보들 중에서 다시 최대를 뽑아서 두 번째로 큰 값을 찾는 기법.
1. 첫 번째 토너먼트 (find MAX) n개의 원소를 한 쌍씩 비교해 올라가면서 최댓값을 찾을 때, 매 비교마다 승자는 다음 라운드로 진출하고 패자는 탈락하므로, 총 n−1번의 비교가 필요.
2. 최댓값과 겨룬 패자(losers) 모으기 토너먼트 트리에서 루트(최댓값)까지 올라오는 과정에서 최댓값과 직접 비교된 후보(패자)는 트리의 높이만큼, 즉 ⌊log2n⌋명. 이들은 “두 번째로 클 수 있는” 유일한 후보들.
3. 패자들 중에서 두 번째 최대값 찾기 이 log2n명의 후보를 다시 최대를 뽑는 또 다른 “작은 토너먼트”라고 보면, log2n−1번의 비교로 그 안에서 최댓값(=원래 전체에서 두 번째로 큰 값)을 찾을 수 있음.
4. 총 비교 횟수 합산 n−1 + (log2n−1) = n+log2n−2. 첫 토너먼트(전체 최대) + 패자들 토너먼트(두 번째 최대)
즉, 전체 과정에서 n−1 + log2n−1 비교를 수행하므로, 최종적으로 n+log2n−2n 번의 비교를 하는 셈.
How to keep track of losers to MAX
One way to do this is to maintain the linked lists of keys that lose to each undefeated keys. This requires O(n) extra space.
최댓값을 찾는 “토너먼트 방식”에서, “최댓값”이 되기까지 직접 비교를 통해 패배(lose)한 키들을 모두 모아두려면 다음과 같이 하면 됨.
1. 각 키에 연결 리스트(linked list) 준비 배열의 각 원소(키)마다 자신에게 패배한(lose) 상대 키들을 저장할 수 있는 빈 연결 리스트를 하나씩 만든다. 이때 연결 리스트 전체를 합치면 최대 n−1개의 요소가 저장되므로, 추가 공간 O(n) 만 필요.
2. 토너먼트 진행하면서 패자 기록 두 키 x 와 y 를 비교해 승자를 w=max(x,y), 패자를 l=min(x,y)라고 할 때, 승자인 w의 연결 리스트에 l 을 “push” 하듯 추가. 이렇게 하면, 나중에 w가 최종 승자가 되었을 때, “w에게 패배한 키들” 이라는 연결 리스트가 고스란히 남게 됨.
3. 두 번째 최댓값 찾기 최종 승자 w∗의 연결 리스트에는, “w∗가 이긴(compare) 모든 상대”가 들어 있음. 두 번째로 큰 값은 이 리스트 중 최댓값이므로, 이 리스트를 한 번 탐색하며 최대를 찾으면 됨. 리스트 길이는 토너먼트 트리 높이(⌊log2n⌋)이므로, 이 단계 비교 횟수는 O(logn).
4. 요약 - 공간 복잡도: 승자별 패자 기록용 연결 리스트 총합으로 O(n) - 시간 복잡도: 1) 전체 토너먼트 = n−1 비교 2) 최종 승자 패자 리스트 탐색 = O(logn) 비교 → 총 n+logn−2 비교
이렇게 연결 리스트를 유지하면 “누가 누구에게 졌는지”를 일일이 다시 기억할 필요 없이, 최댓값에 패배한 후보들만 빠르게 추려낼 수 있음.
Searching: general selection problem
Given keys, x1,x2,...,xn, find the kth smallest (or the kth largest) key.
findMax: finding the largest key (k=n)
findMin: finding the smallest key (k=1)
find2ndMax: finding the 2nd largest key (k=n-1)
findMedian: k= n/2
Use divide-and-conquer (i.e., quicksort) to find k-th MIN
Let's say pivot is at i-th index
if k=i, pivot is k-th MIN
if k<i, recursively find MIN on sublist with i-1 length
if k>i, recursively find MIN on sublist with n-i length
Pseudo-code
Input: a(list), k
Output: k-th MIN
selection(left, right, k, a)
{
if(left equals right)
return a[left]
else
{
pivot = partition(left, right, a)
if(k equals pivot)
return a[pivot]
else if(k is less than pivot)
return selection(left, pivot – 1, k);
else
return selection(pivot + 1, right, k);
}
}
Unfortunately, it has the same worst-case time complexity as Quicksort, given by O(n^2).
The careful choice of the pivot element improves on worst-case quadratic time, so called the "median-of-medians rule". Next we show briefly how this can be done.
The "Median-of-Medians" rule:
Assume n=5(2r+1) for some r>0. We choose r=5.
divide n keys into n/5 sets of 5 keys each. 5개씩 그룹 나누어 각 그룹 중앙값 구함.
find the median mi of each set, where 1<=i<=n/5.
중앙값들로 다시 중앙값 m∗ 찾기(재귀 호출), that is, S={m_1,m_2,...,m_n/5} and k=n/10.
n/5개의 원소 m_1,m_2,...,m_n/5에 대해서 k=n/10으로 하여 이 함수를 다시 재귀적 호출, 중앙값들의 중앙값인 m*를 구한다.
compare each key in A and D to m*.
Let S1=C∪{keys < m* in A, D} and S2=B ∪{keys > m* in A, D}.
A,D에 있는 원소들 중 m*보다 작은 원소
A,D에 있는 원소들 중 m*보다 큰 원소
if |S1+1|=k, then m* is the k-th smallest key
else if k<=|S1| then select (S1,k) S1에서 k번째로 작은 값 찾기
else select (S2, k-|S1|-1) S2에서 k-|S1|-1번째로 작은 값 찾기
1. 5개씩 그룹으로 나누고 중앙값 뽑기 전체 n개의 키를 임의 순서로 5개씩 묶는다. 각 그룹(크기 최대 5)의 중앙값을 삽입 정렬 등으로 O(1)에 뽑아낸다. 총 그룹 수는 ⌈n/5⌉이므로, 이 단계 비용은 O(n).
2. 중앙값들의 중앙값 m∗ 구하기 뽑아낸 ⌈n/5⌉개의 중앙값을 다시 QuickSelect(재귀)로 처리하여 전체 중앙값을 구한다. 이 단계 비용은 T(n/5).
3. m∗로 배열 분할(Partition) 원래 배열을 <m∗, =m∗, >m∗ 세 부분으로 나눈다. 보장: 적어도 3n/10개 이상이 <m∗에, 적어도 3n/10개 이상이 >m∗에 속한다. 따라서 남는(가장 큰) 부분도 최대 7n/10개 이하다. 이 단계 역시 전체 순회 한 번이므로 O(n)
4. 재귀 호출 찾고자 하는 순위 k가 < 왼쪽 크기면 왼쪽(≤3n/10)만, > 왼쪽+중앙값 개수면 오른쪽(≤7n/10)만 재귀 최악의 재귀 호출 비용은 T(7n/10)
전체 비용 합산 T(n) = O(n) + T(n/5) + T(7n/10) = O(n) (그룹 나누고 중앙값 뽑고 분할까지) + (중앙값들의중앙값 찾기) + (가장 큰 재귀부분 호출)
Backup slide: general selection problem
“왜 Median‐of‐Medians 로 분할하면 최악에도 T(n)=O(n)이 보장되는지”를 • 그룹 크기(n/5중간값) • 피벗 기준 좌우 크기(≤7n/10) • 점화식 전개 등을 통해 수학적으로 증명하는 보충 자료
Time complexity:
Therefore, with this method, the algorithm is called “quickSelect”
Comparisons
For each set of 𝑛/5 sets, find median among 5 keys: 6𝑛/5
For the partition, compare n keys: n
Recursive calls
Find median-of-medians on 𝑛/5 on medians: W(𝑛/5)
Recursive call on left or right sub array:W(7𝑛/10)
Find the median among 5 keys
문제 5개의 원소 A,B,C,D,E 중에서 중앙값(3번째로 작은 값)을 찾고자 합니다.
비교 횟수 대회 이론이나 정보 이론 상, 5개에서 정확한 중앙값을 구하려면 최소 6번의 비교가 필요합니다.
한 가지 가능한 비교 순서 1) A vs. C → 더 큰 쪽을 W1, 작은 쪽을 L1으로 표시 2) B vs. D → 승자 W2, 패자 L2 3) W1 vs. W2 → 이 두 중 가장 큰 값을 W3, 작은 값을 L3 4) L3 vs. E → 승자 W4, 패자 L4 5) L4 vs. min(W1,W2) → 승자 W5 6) W5 vs. min(L1,L2) 또는 추가 비교를 통해 최종 중앙값 도출 이 과정을 통해 “5개 중 세 번째로 큰(=세 번째로 작은) 원소”를 정확히 분리해낼 수 있습니다.
왜 6번이 필요한가? 임의로 5개를 비교해 보면, 5개 중 3번째 위치를 결정짓기 위해서는 “누가 1,2위고, 누가 4,5위인지를 명확히 구분”해야 하기 때문. 4번 비교만으로는 상위 2개의 후보가, 하위 2개의 후보가 뒤바뀔 수 있는 경우가 남아 있고, 5번 비교로는 상·하위 그룹 중 하나만 확정될 뿐 전체 중앙값까지 좁히기에는 불충분합니다. 6번 비교를 통해야만 “중앙값 후보 그룹”을 명확히 가려낼 수 있습니다.
Median‐of‐Medians 맥락에서 이 6회 비교 과정을 n/5번 반복하여, “n/5개의 그룹별 중앙값”을 모두 구한 뒤, 그중 중앙값(m∗)을 찾는 재귀 단계의 기초가 됨.
