정렬과 비교 기반 하한 (Sorting and lower bounds)

1. 오프닝: 왜 정렬에서 lower bound를 배우는가

정렬(sorting, Sortieren)은 AUD에서 가장 익숙해 보이지만, 실제 시험에서는 가장 자주 함정을 만드는 주제입니다. 학생은 보통 InsertionSort는 \(n^{2}, \text{MergeSort}\)n², MergeSort는 n log n, QuickSort도 n log n, RadixSort는 linear라고 외웁니다. 하지만 시험 문장은 그렇게 친절하지 않습니다. '모든 정렬 알고리즘은 \(\Omega(n \log n)\)Ω(n log n)이 필요하다' 같은 문장이 나오면, 그 문장이 comparison-based model을 말하는지, worst-case comparisons를 말하는지, non-comparison sort를 제외했는지 확인해야 합니다. 이 장의 목표는 알고리즘 이름 암기가 아니라, 어떤 정보 모델에서 어떤 bound가 성립하는지 스스로 분해해 말하는 능력입니다. 정렬은 작은 카드 놀이처럼 보이지만 사실은 알고리즘이 입력 순서에 대한 정보를 얼마나 빨리 얻을 수 있는가를 묻는 첫 정보 이론 문제입니다.

시험 답안 첫 문장: 이 lower bound는 correct comparison-based sorting의 worst-case comparisons에 대한 명제입니다.

2. 선수 지식과 용어 지도

먼저 입력은 배열 A라고 생각합니다. 각 원소는 key(Schluesselwert)를 가지고 있고, 그 key들에는 \(\text{total} \text{order}(\text{totale} \text{Ordnung}) \le \)total order(totale Ordnung) ≤가 있다고 가정합니다. 객체 전체가 key는 아닐 수 있습니다. 학생 기록을 점수순으로 정렬한다면 점수가 key이고 이름, 학번, 주소 같은 나머지는 satellite data(Satellitendaten)입니다. 같은 점수를 가진 학생 둘의 상대 순서를 유지해야 한다면 stability(stabil)가 중요해집니다. 또한 in-place는 추가 메모리 성질입니다. stable은 같은 key의 순서 보존, in-place는 extra storage가 작은지에 관한 말이므로 서로 독립입니다. 마지막으로 worst-case, expected, average, best case를 구분해야 합니다. QuickSort를 말할 때 특히 randomized expected와 worst-case를 섞으면 바로 틀립니다.

• key: 정렬 기준이 되는 값
• satellite data: key와 함께 움직여야 하는 나머지 정보
• stable: 같은 key의 상대 순서 보존
• in-place: 추가 저장공간이 작음
• comparison-based: 순서 정보를 비교 결과로만 획득

3. 정렬 문제의 정확한 정의

sorting problem은 입력 sequence를 받아 같은 객체들을 key 순서에 맞게 재배열해서 출력하는 문제입니다. 여기서 '같은 객체들'이라는 말이 중요합니다. 출력이 정렬되어 있다는 sorted 조건만으로는 충분하지 않습니다. 원래 원소가 사라지거나 새 원소가 생기면 sorted라도 정렬 알고리즘의 출력이 아닙니다. 따라서 correctness를 엄밀히 말할 때는 sorted order와 permutation 또는 multiset preservation을 함께 말합니다. 이 관점은 loop invariant 페이지와 연결됩니다. InsertionSort correctness proof에서 sorted prefix뿐 아니라 원소 보존을 말해야 하는 이유도 같습니다. 정렬의 output은 key 순서에 맞아야 하고, satellite data는 해당 key와 함께 그대로 이동해야 합니다.

4. comparison-based sorting 모델

comparison-based sorting(vergleichsbasiertes Sortieren)은 알고리즘이 원소들의 상대 순서를 오직 비교 질문으로만 배운다는 모델입니다. 질문은 예를 들어 \(A[i] \le A[j]\)A[i] ≤ A[j]? 입니다. 답은 yes 또는 no입니다. InsertionSort, MergeSort, QuickSort, HeapSort는 모두 comparison-based로 볼 수 있습니다. 알고리즘이 swap을 하거나 array index를 읽는다고 해서 comparison-based가 아닌 것은 아닙니다. 핵심은 순서 정보가 어디서 오는가입니다. 순서 정보가 비교 결과뿐이면 comparison-based입니다. 반대로 key가 0..K 범위의 integer라는 사실을 이용해 count array index로 직접 들어가면 다른 모델입니다. 이 모델 구분을 놓치면 lower bound를 잘못 적용하게 됩니다.

판별 질문: 이 알고리즘은 order information을 비교 결과만으로 얻는가?

5. decision tree의 그림

comparison sort의 한 실행을 decision tree(Entscheidungsbaum)로 그릴 수 있습니다. root는 첫 비교입니다. 비교 결과가 yes이면 왼쪽 edge, no이면 오른쪽 edge로 내려간다고 합시다. 다음 node는 다음 비교입니다. 입력에 따라 알고리즘은 root에서 시작해 어떤 leaf에 도착합니다. leaf는 알고리즘이 더 이상 구분하지 않고 같은 종류의 최종 결정을 내리는 곳입니다. worst-case에서 m번 비교한다는 말은 이 decision tree의 깊이가 m 이하라는 뜻입니다. binary tree에서 깊이 m이면 leaf는 최대 \(2^{m}\)2ᵐ개입니다. 실제 알고리즘의 tree는 균형이 안 맞거나 없는 branch가 있을 수 있으므로 'exactly'가 아니라 'at most'입니다.

6. 왜 n!개의 leaf가 필요한가

서로 다른 n개 key를 정렬한다고 합시다. 가능한 입력 순열은 n!개입니다. correct sorter는 이 순열들을 충분히 구분해야 합니다. 만약 서로 다른 두 입력 순열이 같은 leaf에 도착하면 알고리즘은 같은 비교 결과 sequence를 봤고, leaf에서 같은 최종 결정을 합니다. 하지만 두 입력의 원래 순서는 다르므로, 같은 최종 결정이 항상 둘 다에 맞을 수 없습니다. 더 엄밀히 말하면 comparison 결과만으로 두 permutation을 구분하지 못했는데 서로 다른 sorted order를 요구하는 경우가 생기고, 그러면 적어도 하나는 잘못됩니다. 그래서 correct comparison sorter의 decision tree에는 적어도 n!개의 leaf가 필요합니다.

n!은 출력 값의 개수가 아니라, 서로 다른 n개 key의 가능한 입력 순열 수입니다.

7. lower bound 증명 한 줄에서 네 줄로 풀기

이제 두 사실을 결합합니다. m번 비교하는 decision tree는 leaf가 최대 \(2^{m}\)2ᵐ개입니다. 올바른 comparison sort는 n!개의 입력 순열을 구분해야 하므로 leaf가 적어도 n!개 필요합니다. 따라서 \(2^{m} \ge n!\)2ᵐ ≥ n!이어야 합니다. 양쪽에 log2를 취하면 \(m \ge \log_{2}(n!)\)m ≥ log2(n!)입니다. 그리고 log2(n!)은 \(\Omega(n \log n)\)Ω(n log n)입니다. 예를 들어 n! 안에는 n/2보다 큰 항이 n/2개 정도 있으므로 log(n!)은 적어도 (n/2)log(n/2)이고, 이는 \(\Omega(n \log n)\)Ω(n log n)입니다. 결론은 모든 correct comparison-based sorting algorithm은 worst case에서 \(\Omega(n \log n)\)Ω(n log n) comparisons가 필요하다는 것입니다.

8. lower bound의 scope를 정확히 말하기

가장 큰 시험 함정은 '모든 sorting은 \(\Omega(n \log n)\)Ω(n log n)'이라고 줄여 말하는 것입니다. 이 문장은 거짓입니다. 정확한 문장은 comparison-based sorting에 대한 worst-case comparison lower bound입니다. CountingSort는 bounded integer key range를 사용하고, RadixSort는 digit과 bucket을 사용합니다. 이들은 비교 질문만으로 순서 정보를 얻는 모델이 아닙니다. 따라서 decision-tree proof의 전제가 깨집니다. 그렇다고 공짜로 빠른 것은 아닙니다. key range K, digit 수 d, bucket 수 D, 추가 배열, stable pass 같은 비용과 전제가 붙습니다. 즉 lower bound를 깨는 것이 아니라 다른 문제 모델로 이동하는 것입니다.

기수 정렬(RadixSort)은 반례가 아니라 비교 모델 밖의 알고리즘입니다.

9. InsertionSort를 시험형으로 이해하기

InsertionSort는 왼쪽에 이미 sorted prefix를 유지하고, 새 key를 그 prefix 안의 맞는 위치로 끼워 넣습니다. 이미 정렬된 입력이면 각 단계에서 while 조건이 거의 바로 실패하므로 비교와 이동이 적고 best case는 \(\Theta(n)\)Θ(n)입니다. 반대로 역순 입력이면 새 key가 매번 prefix의 맨 앞으로 가야 하므로 i번째 단계에서 거의 i번 shift합니다. 합은 \(1+2+...+(n-1)=\Theta(n^{2})\)1+2+...+(n-1)=Θ(n²)입니다. InsertionSort는 같은 key를 가진 원소를 서로 지나치게 이동시키지 않도록 구현하면 stable이고, 배열 안에서 shift만 하므로 in-place로 볼 수 있습니다. 하지만 worst-case bound는 comparison lower bound보다 느립니다. 작은 입력이나 거의 정렬된 입력에서 실용적이라는 말과 asymptotic worst-case가 좋다는 말은 다릅니다.

10. MergeSort: lower bound에 맞는 comparison sort

MergeSort는 divide and conquer의 대표 예시입니다. 배열을 반으로 나누고 두 half를 재귀적으로 정렬한 뒤, 두 sorted half를 한 번 scan해서 merge합니다. 그래서 recurrence는 \(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)이고 Master theorem case 2로 \(\Theta(n \log n)\)Θ(n log n)입니다. comparison lower bound가 \(\Omega(n \log n)\)Ω(n log n)이므로 MergeSort는 comparison-based model에서 asymptotically optimal입니다. 단, lecture merge는 temporary array B를 사용합니다. 따라서 그 구현은 not in-place입니다. stability는 merge tie 처리에 달려 있습니다. 왼쪽과 오른쪽 원소의 key가 같을 때 왼쪽 원소를 먼저 output하면 원래 상대 순서가 보존됩니다.

11. QuickSort: expected와 worst를 분리하기

QuickSort는 pivot을 고르고, pivot보다 작은 원소와 큰 원소를 partition한 뒤 양쪽을 재귀 정렬합니다. 균형이 좋으면 recursion depth가 log n에 가깝고 각 level의 partition 비용이 \(\Theta(n)\)Θ(n)이므로 n log n이 기대됩니다. 하지만 pivot이 계속 최솟값이나 최댓값처럼 나쁘게 선택되면 한쪽 subproblem은 비고 다른 쪽은 n-1이 됩니다. 이때 \(T(n)=T(n-1)+\Theta(n)=\Theta(n^{2})\)T(n)=T(n-1)+Θ(n)=Θ(n²)입니다. randomized QuickSort의 expected \(\Theta(n \log n)\)Θ(n log n)은 random choice에 대한 기대값이지, 모든 실행에서 worst-case를 막는 보장은 아닙니다. MC에서 'QuickSort is \(\Theta(n \log n)\)Θ(n log n)'이라는 문장이 나오면 expected인지 average인지 worst인지 먼저 물어야 합니다.

12. CountingSort와 RadixSort의 모델 전환

CountingSort는 key가 작은 integer range 0..K에 있다는 전제를 사용합니다. count array에 직접 접근해 각 key의 개수를 세므로 comparison tree 모델과 다릅니다. runtime과 memory는 보통 \(\Theta(n+K)\)Θ(n+K)입니다. K가 n에 비해 작거나 제한되어야 linear처럼 좋습니다. RadixSort는 key를 digit으로 나누고 각 digit에 대해 bucket 또는 stable counting pass를 수행합니다. lecture의 LSD 방식은 least significant digit부터 처리하며, 이전 digit에서 만들어 둔 순서를 다음 pass가 깨지 않도록 stable pass가 필요합니다. runtime은 \(O(d(n+D))\)O(d(n+D))이고, Sheet04의 bit grouping에서는 b-bit key를 r-bit digit으로 묶어 \(O((b/r)(n+2^{r}))\)O((b/r)(n+2^r))가 나옵니다.

13. stability와 in-place를 runtime에서 떼어내기

stable(stabil)은 같은 key를 가진 원소들의 원래 상대 순서가 보존된다는 뜻입니다. 입력 [2a, 1, 2b]를 숫자 key로 정렬할 때 stable output은 [1, 2a, 2b]입니다. [1, 2b, 2a]도 key만 보면 sorted이지만 stable하지 않습니다. in-place는 추가 메모리를 얼마나 쓰는지에 관한 성질입니다. MergeSort는 stable하게 만들 수 있지만 lecture version은 temporary array B를 쓰므로 not in-place입니다. QuickSort는 보통 in-place에 가깝게 구현되지만 stable하지 않은 경우가 많습니다. 따라서 'stable이면 in-place'나 'not in-place이면 unstable' 같은 연결은 모두 잘못입니다.

14. 알고리즘 비교표를 읽는 순서

정렬 알고리즘을 비교할 때는 네 칸을 항상 같은 순서로 채우세요. 첫째 runtime: best, worst, expected 중 무엇인지. 둘째 stable 여부. 셋째 in-place 여부. 넷째 model과 precondition입니다. InsertionSort는 거의 정렬된 입력에서는 빠르지만 worst는 quadratic입니다. MergeSort는 comparison sort로 optimal한 n log n이지만 extra array가 필요합니다. QuickSort는 실전에서 빠르고 expected n log n이지만 \(\text{worst} n^{2}\)worst n²입니다. CountingSort와 RadixSort는 특정 key representation이 있어야 빠릅니다. 시험 답안에서 이 네 칸 중 하나라도 생략하면 참인 문장을 너무 넓게 말해 거짓으로 만들 수 있습니다.

15. proof intuition: 정보량으로 보기

lower bound proof의 직관은 정보량입니다. n개의 서로 다른 물건을 줄 세우는 가능한 세계는 n!개입니다. 비교 하나는 그 세계를 두 그룹으로 나누는 질문입니다. 가장 운 좋게 반반 나누어도 m번 질문 후 구분 가능한 세계는 최대 \(2^{m}\)2ᵐ개입니다. n!개 세계를 다 구분하려면 \(2^{m}\)2ᵐ이 n!보다 작으면 안 됩니다. 이 설명은 formal proof와 같은 구조를 가집니다. formal proof에서는 '세계'를 input permutation, '질문'을 comparison, '질문 기록'을 root-to-leaf path라고 부릅니다. 직관과 formal term을 연결해 말하면 oral exam에서 매우 강한 답안이 됩니다.

16. Sheet03와 Sheet04가 묻는 방식

Sheet03 쪽은 divide and conquer sorting, MergeSort/QuickSort 실행 그림, stability, recurrence 감각과 연결됩니다. Sheet04 쪽은 lower bound와 RadixSort를 직접 묻습니다. 특히 bit grouping 문제는 b-bit number를 r-bit씩 묶으면 bucket 수가 \(2^{r}\)2^r이고 pass 수가 b/r이라는 사실을 요구합니다. 따라서 \(O((b/r)(n+2^{r}))\)O((b/r)(n+2^r))에서 각 기호가 무엇을 뜻하는지 말할 수 있어야 합니다. r을 키우면 pass는 줄지만 bucket 수가 폭발합니다. 이 trade-off는 단순 공식 암기가 아니라 digit size 선택 문제입니다. 시험에서는 \(r=\log n\)r=log n같은 선택이 왜 자연스러운지 묻거나, \(b\le \log n\)b≤log n이면 \(r=b\)r=b가 가능하다는 식의 조건 분기를 요구할 수 있습니다.

17. oral exam에서의 60초 답안 구조

60초 답안은 범위를 좁혀야 합니다. 먼저 'comparison-based sorting의 worst-case lower bound'라고 scope를 말합니다. 그 다음 decision tree를 한 문장으로 정의합니다. internal node는 비교, edge는 yes/no, leaf는 구분된 permutation입니다. m comparisons이면 leaf가 최대 \(2^{m}\)2ᵐ개이고, n distinct keys에는 n! permutations가 있으므로 correct sorter는 n!개를 구분해야 합니다. 따라서 \(2^{m} \ge n!, m \ge \log_{2}(n!) = \Omega(n \log n).\)2ᵐ ≥ n!, m ≥ log2(n!) = Ω(n log n).마지막으로 RadixSort/CountingSort는 digit 또는 key range를 쓰므로 이 모델 밖이라고 덧붙이면 완성입니다.

18. deep dive 답안의 추가 포인트

깊게 물어보면 세 가지를 더 붙입니다. 첫째, n! leaf 필요성은 correctness에서 옵니다. 서로 다른 permutation을 같은 leaf로 보내면 같은 comparison history를 보았기 때문에 같은 결정을 내리고, 적어도 하나의 입력에서 wrong output이 됩니다. 둘째, \(\log_{2}(n!) = \Omega(n \log n)\)log₂(n!) = Ω(n log n)의 근거를 말합니다. n!의 뒤쪽 절반 항들은 모두 n/2 이상이므로 그 곱은 n/2를 n/2번 곱한 값 이상이고, 따라서 \(\log(n!) \ge (n/2)\log(n/2)\)log(n!) ≥ (n/2)log(n/2)입니다. 셋째, lower bound는 comparison 수에 대한 명제이지 memory movement나 arithmetic operation 전체에 대한 자동 명제가 아닙니다. 이 세 점을 붙이면 증명 intuition, formal inequality, model caveat가 모두 들어간 답안이 됩니다.

19. lower bound를 작은 숫자로 체감하기

\(n=3\)n=3이면 가능한 순열은 6개입니다. 2번 비교하면 yes/no 결과열은 최대 4개뿐입니다. 그래서 어떤 comparison sorter도 모든 입력을 2번 비교 안에 끝낼 수 없습니다. \(n=4\)n=4이면 가능한 순열은 24개입니다. 4번 비교는 최대 16개 leaf만 만들 수 있으므로 부족하고, 5번 비교는 최대 32개 leaf capacity를 가지므로 정보량 관점에서는 가능성이 생깁니다. 여기서 주의할 점은 5번이면 반드시 실제 알고리즘이 존재한다는 뜻은 아닙니다. lower bound는 필요한 최소량의 아래쪽 제한입니다. 시험에서 이 예시를 말하면 inequality가 단순 공식이 아니라 구분해야 할 경우의 수와 질문 capacity의 비교라는 점이 분명해집니다.

20. InsertionSort 손실 없이 증명하기

InsertionSort를 설명할 때는 runtime만 말하지 말고 correctness 직관도 함께 붙이면 좋습니다. outer loop의 시작 시점마다 왼쪽 prefix는 이미 sorted이고 원래 그 prefix에 있던 원소들을 같은 개수로 포함합니다. 새 key를 꺼내 prefix 안에서 자기보다 큰 원소들을 오른쪽으로 밀고 빈 자리에 넣으면 prefix 길이가 하나 늘어납니다. 이동만 했으므로 원소 보존이 깨지지 않고, key보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 남으므로 sorted도 유지됩니다. runtime은 이 shift 수가 입력 상태에 따라 달라진다는 데서 나옵니다. sorted input에서는 거의 shift가 없고, reverse input에서는 매번 prefix 전체를 밀게 됩니다.

21. MergeSort merge를 stable하게 읽는 법

MergeSort의 merge 단계는 두 sorted list의 앞 원소를 비교해 더 작은 것을 output으로 보내는 반복입니다. 두 앞 원소의 key가 같을 때 왼쪽 half의 원소를 먼저 보내면, 원래 배열에서 왼쪽에 있던 equal-key 원소가 계속 먼저 남습니다. 이것이 left-first tie rule이 stability를 보존하는 이유입니다. 반대로 오른쪽을 먼저 보내면 두 half에 나뉜 같은 key들의 상대 순서가 바뀔 수 있습니다. 또 merge를 빠르게 하려면 보통 temporary array B가 필요합니다. 이 구현 세부사항 때문에 lecture version의 MergeSort는 stable하게 만들 수 있어도 in-place는 아니라고 말하는 것이 안전합니다.

22. QuickSort partition에서 생기는 두 가지 오해

첫 번째 오해는 partition이 한 번에 전체를 정렬한다고 생각하는 것입니다. partition은 pivot보다 작은 쪽과 큰 쪽을 나눌 뿐, 각 쪽 내부 순서는 아직 정렬되어 있지 않을 수 있습니다. 그래서 recursive sorting이 필요합니다. 두 번째 오해는 pivot을 무작위로 고르면 worst case가 사라진다고 생각하는 것입니다. 무작위 선택은 나쁜 pivot sequence가 나올 확률을 낮추어 expected runtime을 좋게 만듭니다. 하지만 특정 실행에서는 계속 나쁜 pivot이 나올 수 있고, worst-case upper bound는 여전히 quadratic입니다. 시험에서는 randomized expected, average case, worst case를 섞는 문장을 특히 조심해야 합니다.

23. HeapSort를 비교표에 넣는 이유

이 페이지의 중심은 lower bound지만, 비교표에서 HeapSort를 떠올릴 수 있어야 합니다. HeapSort는 heap property를 사용하지만 원소의 order information은 비교를 통해 얻습니다. 따라서 comparison-based sorting에 속하고 lower bound의 적용 대상입니다. 일반적인 array heap version은 in-place 장점이 있고 worst-case \(\Theta(n \log n)\)Θ(n log n)을 보장하지만 stable하지 않은 것으로 다루는 것이 보통입니다. AUD의 heap 자체는 advanced data structures에서 더 자세히 다루지만, sorting 비교 문장에서는 MergeSort, QuickSort와 함께 runtime/stable/in-place/model 네 칸으로 비교할 수 있어야 합니다.

24. CountingSort를 안전하게 말하는 문장

CountingSort는 'linear sorting'이라고만 말하면 위험합니다. 안전한 문장은 다음과 같습니다. key가 0..K 같은 bounded integer range에 있고, count/output arrays를 사용할 수 있으면 CountingSort는 \(\Theta(n+K)\)Θ(n+K)에 정렬할 수 있습니다. K가 n에 비해 작으면 linear처럼 보이지만, K가 매우 크면 n보다 K가 지배합니다. 또 stable CountingSort는 output을 채우는 방향과 prefix count 처리가 중요합니다. 이 페이지에서는 세부 구현보다 모델 구분이 핵심입니다. CountingSort는 비교 질문만으로 순서 정보를 얻는 것이 아니라 key 값을 array index처럼 사용하기 때문에 decision-tree lower bound의 전제가 아닙니다.

25. RadixSort LSD stable pass 직관

LSD RadixSort는 least significant digit부터 처리합니다. 처음에는 1의 자리로 bucket에 넣고 stable하게 다시 모읍니다. 다음에는 10의 자리로 bucket에 넣습니다. 이때 같은 10의 자리 bucket 안에서는 이전 pass에서 만들어 둔 1의 자리 순서가 유지되어야 합니다. 그래서 각 digit pass가 stable해야 합니다. stable하지 않은 pass를 쓰면 낮은 자리에서 이미 정리된 정보가 높은 자리 pass에서 섞여 버립니다. 즉 RadixSort의 correctness는 'digit을 본다'만으로 끝나지 않고, pass 순서와 stable bucket collection이 함께 필요합니다. 이 점은 Sheet04 스타일 MC에서 자주 쓰기 좋은 함정입니다.

26. bit grouping trade-off를 말로 설명하기

b-bit number를 r-bit씩 묶는다는 말은 digit 하나가 r bits라는 뜻입니다. r bits는 \(2^{r}\)2^r가지 값을 가질 수 있으므로 bucket도 \(2^{r}\)2^r개가 필요합니다. 전체 b bits를 처리하려면 b/r번 pass가 필요합니다. 각 pass는 n개 원소를 bucket에 넣고 bucket들을 다시 읽어야 하므로 \(O(n+2^{r})\)O(n+2^r)입니다. 따라서 전체가 \(O((b/r)(n+2^{r}))\)O((b/r)(n+2^r))입니다. r을 크게 잡으면 pass 수 b/r은 줄지만 bucket 수 \(2^{r}\)2^r이 커집니다. r을 작게 잡으면 bucket은 적지만 pass가 많아집니다. 시험에서 r 선택을 묻는다면 이 균형을 먼저 말한 뒤 조건에 맞는 값을 대입하면 됩니다.

27. MC exact-one 문제를 푸는 절차

정렬 MC를 보면 바로 참거짓을 고르지 말고 네 단계로 검사하세요. 첫째, 문장에 comparison-based라는 모델 제한이 있는가. 둘째, worst-case, average, expected, best 중 어느 case인지 명시되어 있는가. 셋째, stable과 in-place 같은 성질을 runtime처럼 말하고 있지 않은가. 넷째, CountingSort/RadixSort라면 key range, digit 수, bucket 수 조건이 빠져 있지 않은가. 예를 들어 'QuickSort is \(\Theta(n \log n)\)Θ(n log n)'은 너무 넓습니다. randomized expected라면 맞을 수 있지만 worst-case statement라면 틀립니다. 이 절차를 습관화하면 그럴듯한 문장 하나에 끌려가지 않습니다.

28. MC exact-two 문제에서의 조합 함정

exactly two correct 형식에서는 한 문장을 고른 뒤 안심하면 안 됩니다. 정렬 관련 보기들은 보통 하나는 model scope, 하나는 runtime case, 하나는 stability, 하나는 Radix/Counting precondition을 섞습니다. 두 정답을 모두 고르려면 각 보기의 조건 누락을 독립적으로 확인해야 합니다. 예를 들어 'MergeSort is stable'은 tie rule이 left-first라는 구현 조건을 암묵적으로 요구할 수 있습니다. 'RadixSort runs in \(O(n)\)O(n)'은 d와 D가 상수라는 조건이 없으면 너무 강합니다. 정답 후보를 표시한 뒤에는 반례를 한 줄씩 떠올려 보세요. 반례가 바로 나오면 그 보기는 보통 false입니다.

29. written proof 답안 템플릿

서술형으로 lower bound를 쓰라는 문제가 나오면 다음 템플릿을 사용하세요. 먼저 'consider any correct comparison-based sorting algorithm on n distinct keys'라고 범위를 둡니다. 그 알고리즘의 possible executions를 decision tree로 표현합니다. 각 internal node는 comparison, 각 outgoing edge는 comparison result입니다. worst-case m comparisons이면 depth m이고 leaf 수는 \(\text{at} \text{most} 2^{m}\)at most 2ᵐ입니다. correctness 때문에 n! input permutations must be distinguished, so at least n! leaves are necessary. 따라서 \(2^{m} \ge n!, \text{hence} m \ge \log_{2}(n!) = \Omega(n \log n).\)2ᵐ ≥ n!, hence m ≥ log2(n!) = Ω(n log n).마지막 문장에 RadixSort caveat를 덧붙이면 모델 이해까지 보여 줍니다.

30. oral examiner가 파고들 때 방어하기

구술에서 examiner가 '왜 같은 leaf면 틀리나요?'라고 물으면, 같은 leaf는 같은 comparison results를 뜻하므로 알고리즘이 두 입력을 구분할 정보가 없다고 답하세요. 정렬 output은 입력 객체들의 permutation이어야 하며, 서로 다른 input order가 같은 comparison history로 합쳐지면 적어도 하나의 입력에서 필요한 상대 순서를 보장할 수 없습니다. 'RadixSort는요?'라고 물으면 model이 다르다고 답합니다. digit access는 comparison result가 아니라 key representation을 직접 사용하는 operation입니다. '그럼 lower bound가 의미 없나요?'라고 물으면 comparison model 안에서는 tight하고, MergeSort/HeapSort가 \(\Theta(n \log n)\)Θ(n log n)으로 맞춘다고 답하세요.

31. 개념 연결: asymptotic notation과 recurrence

이 장은 두 이전 개념과 바로 연결됩니다. Asymptotic notation에서는 Omega가 lower bound라는 것을 배웠습니다. 여기서 \(\Omega(n \log n)\)Ω(n log n)은 어떤 특정 알고리즘의 running time 분석이 아니라 모델 전체에 대한 lower bound입니다. Recurrences에서는 MergeSort의 \(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)을 풀어 \(\Theta(n \log n)\)Θ(n log n)을 얻었습니다. 따라서 MergeSort upper bound와 comparison lower bound를 합치면 comparison sorting model에서 asymptotically optimal이라는 결론이 나옵니다. 이 연결을 말하면 단순히 정렬 알고리즘 표를 외운 것이 아니라, proof와 algorithm analysis를 함께 이해했다는 인상을 줍니다.

32. 마지막 자기 점검

페이지를 닫기 전에 다음 다섯 문장을 말로 완성해 보세요. 첫째, comparison-based sorting은 무엇만으로 순서 정보를 얻는다. 둘째, m번 비교는 최대 몇 개의 leaf를 만든다. 셋째, n distinct keys에는 몇 개의 input permutations가 있다. 넷째, lower bound의 정확한 scope는 무엇이다. 다섯째, RadixSort가 이 lower bound의 직접 적용 대상이 아닌 이유는 무엇이다. 이 다섯 문장을 막힘없이 말하면 기본기는 완성입니다. 그 다음에는 InsertionSort, MergeSort, QuickSort, CountingSort, RadixSort를 runtime/stable/in-place/model 네 칸으로 비교하면 시험형 답안이 됩니다.

33. 확장 MC 함정 해설 세트

아래 문장들은 실제 시험에서 한두 단어만 바뀌어도 참거짓이 바뀌는 유형입니다. 각 문장을 볼 때 먼저 빠진 조건을 찾고, 그 조건을 넣으면 참이 되는지 또는 그래도 거짓인지 판단하세요.

• 모든 correct comparison-based sorting algorithm은 worst case에서 \(\Omega(n \log n)\)Ω(n log n) comparisons가 필요하다. 이 문장은 scope가 정확하므로 참입니다. time이라고 쓰지 않고 comparisons라고 쓴 점도 중요합니다.
• 모든 sorting algorithm은 worst case에서 \(\Omega(n \log n)\)Ω(n log n) comparisons가 필요하다. comparison-based가 빠져 있으므로 거짓입니다. CountingSort와 RadixSort는 comparison count로만 설명되지 않는 모델입니다.
• 모든 comparison-based sorting algorithm은 average case에서 \(\Omega(n \log n)\)Ω(n log n) comparisons가 필요하다. 이 페이지의 decision-tree proof는 worst-case depth를 직접 다룹니다. average lower bound는 별도 논의가 필요하므로 이 문장만으로는 안전하지 않습니다.
• MergeSort는 comparison-based sorting이므로 \(\Omega(n \log n)\)Ω(n log n) lower bound의 적용 대상이고, 실제 runtime도 \(\Theta(n \log n)\)Θ(n log n)입니다. 따라서 asymptotically optimal comparison sort라고 말할 수 있습니다.
• MergeSort는 stable하다. 구현 조건이 생략되어 있으므로 조심해야 합니다. merge에서 equal key tie를 왼쪽 원소 먼저 처리하면 stable하다고 말하는 것이 정확합니다.
• MergeSort는 in-place이다. lecture merge가 temporary array B를 사용한다면 거짓입니다. 다른 특수 in-place merge 변형을 일반 lecture statement로 끌어오면 안 됩니다.
• QuickSort는 partition 때문에 항상 balanced recursion tree를 가진다. 거짓입니다. partition은 pivot 기준으로 나눌 뿐이고 pivot이 나쁘면 n-1과 0으로 갈라질 수 있습니다.
• Randomized QuickSort의 expected runtime은 \(\Theta(n \log n)\)Θ(n log n)이다. 보통 참으로 쓰지만, 이것은 random choices에 대한 expected statement입니다. worst-case guarantee로 바꾸면 틀립니다.
• InsertionSort는 comparison lower bound를 위반한다. 거짓입니다. best case \(\Theta(n)\)Θ(n)이 가능해도 lower bound는 모든 입력에 대한 worst-case comparisons를 말합니다.
• InsertionSort는 reverse input에서 \(\Theta(n^{2})\)Θ(n²)이다. 참입니다. 새 key가 매번 prefix 앞까지 이동하므로 shift 합이 1+...+(n-1)이 됩니다.
• stable sort의 output은 항상 유일하다. key가 같은 객체들의 상대 순서를 보존해야 하지만, 서로 다른 key가 없는 부분이나 같은 key 그룹이 여러 개 있을 때 객체 구분 방식에 따라 표현은 달라질 수 있습니다. 핵심은 equal-key relative order입니다.
• in-place algorithm은 stable할 수 없다. 거짓입니다. 두 성질은 독립입니다. InsertionSort는 stable하고 in-place로 구현할 수 있는 대표 예시입니다.
• CountingSort가 \(\Theta(n+K)\)Θ(n+K)이므로 항상 linear이다. K가 입력 크기 n에 비해 제한되어야 linear처럼 말할 수 있습니다. K가 거대하면 K가 runtime과 memory를 지배합니다.
• RadixSort의 \(O(d(n+D))\)O(d(n+D))에서 d와 D는 상수로 가정해도 된다. 문제에서 그런 조건이 주어졌을 때만 가능합니다. 일반 답안에서는 d와 D를 반드시 남겨야 합니다.
• LSD RadixSort에서 각 digit pass의 stability는 선택 사항이다. 거짓입니다. 낮은 digit에서 정리한 순서를 높은 digit pass가 보존해야 전체 정렬이 맞습니다.
• m comparisons이면 decision tree leaf가 \(\text{exactly} 2^{m}\)exactly 2ᵐ개이다. 거짓입니다. binary tree의 최대 leaf capacity가 \(2^{m}\)2ᵐ일 뿐, 알고리즘이 일찍 멈추거나 branch가 비어 있을 수 있습니다.
• n!은 possible output arrays의 값 개수이다. 표현이 부정확합니다. proof에서는 서로 다른 n개 key의 possible input permutations를 셉니다.
• decision tree lower bound는 memory lower bound도 동시에 준다. 거짓입니다. proof는 comparison count에 대한 정보량 argument입니다. memory usage는 별도 분석이 필요합니다.
• HeapSort는 heap을 쓰므로 comparison-based가 아니다. 거짓입니다. heap order 유지와 heapify는 key comparisons로 이루어지므로 일반적인 HeapSort는 comparison-based입니다.
• lower bound가 \(\Omega(n \log n)\)Ω(n log n)이면 모든 comparison sort의 runtime이 \(\Theta(n \log n)\)Θ(n log n)이다. 거짓입니다. lower bound는 그보다 빠를 수 없다는 말이지, 느린 알고리즘이 없다는 말이 아닙니다. InsertionSort worst case는 \(\Theta(n^{2})\)Θ(n²)입니다.

34. 구술 연습: 질문-힌트-모범 답안

혼자 공부할 때는 아래 항목을 한 번에 읽지 말고, 질문만 보고 20초 안에 답한 뒤 힌트와 모범 답안을 확인하세요. 구술 시험에서는 짧고 정확한 scope 설정이 긴 설명보다 먼저입니다.

• 질문: comparison-based sorting이란 무엇인가요? 힌트: 순서 정보의 출처를 말하세요. 답안: 원소들의 순서 정보를 \(A[i] \le A[j]\)A[i] ≤ A[j]같은 비교 결과로만 얻는 정렬 모델입니다.
• 질문: decision tree의 root-to-leaf path는 무엇을 나타내나요? 힌트: 한 입력에서 실행 중 나온 기록입니다. 답안: 특정 입력에 대해 알고리즘이 수행한 비교 결과 sequence입니다.
• 질문: 왜 m번 비교가 \(2^{m}\)2ᵐ보다 많은 경우를 구분할 수 없나요? 힌트: 비교 하나의 answer alphabet입니다. 답안: 각 비교는 yes/no 두 결과뿐이므로 깊이 m binary tree의 leaf 수는 최대 \(2^{m}\)2ᵐ입니다.
• 질문: 왜 n!개의 경우를 구분해야 하나요? 힌트: distinct keys입니다. 답안: 서로 다른 n개 key의 입력 순열이 n!개이고, correct sorting은 이 순열들을 충분히 구분해 올바른 output permutation을 선택해야 합니다.
• 질문: lower bound 결론을 정확히 말해 보세요. 힌트: 네 단어를 빠뜨리지 마세요. 답안: 모든 correct comparison-based sorting algorithm은 worst case에서 \(\Omega(n \log n)\)Ω(n log n) comparisons가 필요합니다.
• 질문: RadixSort가 왜 반례가 아닌가요? 힌트: model이 다릅니다. 답안: RadixSort는 digit과 bucket index를 사용해 key representation에 직접 접근하므로 comparison-only decision tree 모델의 알고리즘이 아닙니다.
• 질문: MergeSort와 lower bound의 관계는? 힌트: upper와 lower를 합치세요. 답안: MergeSort는 comparison-based이고 \(\Theta(n \log n)\)Θ(n log n)이므로 \(\Omega(n \log n)\)Ω(n log n) lower bound에 asymptotically matching합니다.
• 질문: InsertionSort best case가 \(\Theta(n)\)Θ(n)이어도 lower bound와 모순이 아닌 이유는? 힌트: worst-case statement입니다. 답안: lower bound는 모든 입력을 고려한 worst-case comparisons에 대한 명제이고, best case는 특정 쉬운 입력만 봅니다.
• 질문: QuickSort에서 randomized expected와 worst case를 구분하세요. 힌트: pivot sequence입니다. 답안: random pivot에 대한 기대 runtime은 \(\Theta(n \log n)\)Θ(n log n)이지만, pivot이 계속 극단값이면 worst case는 \(\Theta(n^{2})\)Θ(n²)입니다.
• 질문: stable을 [2a,1,2b]로 설명하세요. 힌트: 같은 key 2의 상대 순서입니다. 답안: stable output은 [1,2a,2b]이고 [1,2b,2a]는 sorted지만 stable하지 않습니다.
• 질문: in-place와 stable의 차이는? 힌트: memory vs order. 답안: in-place는 추가 저장공간이 작은지, stable은 같은 key의 상대 순서를 보존하는지에 관한 독립 성질입니다.
• 질문: \(\text{Sheet}04 \text{formula} O((b/r)(n+2^{r}))\)Sheet04 formula O((b/r)(n+2^r))를 유도하세요. 힌트: pass 수와 bucket 수입니다. 답안: r-bit digit은 \(2^{r} \text{buckets}\)2^r buckets를 만들고 b bits를 처리하려면 b/r passes가 필요하며 pass당 \(O(n+2^{r})\)O(n+2^r)이므로 전체가 \(O((b/r)(n+2^{r}))\)O((b/r)(n+2^r))입니다.

35. written answer에서 감점되는 표현 고치기

시험 답안을 쓸 때는 한국어로 이해했더라도 핵심 German/English term을 같이 붙이면 채점자가 의도를 빠르게 확인할 수 있습니다. 아래의 나쁜 표현을 좋은 표현으로 고쳐 쓰는 연습을 하세요.

• 나쁜 표현: 정렬은 n log n보다 빠를 수 없다. 좋은 표현: comparison-based sorting은 worst-case comparisons에서 \(\Omega(n \log n)\)Ω(n log n) lower bound를 가진다.
• 나쁜 표현: RadixSort는 lower bound를 깬다. 좋은 표현: RadixSort는 digit/bucket representation을 쓰는 non-comparison-based sorting이므로 comparison lower bound의 전제 밖에 있다.
• 나쁜 표현: MergeSort는 메모리를 안 쓴다. 좋은 표현: lecture merge pseudocode는 temporary array B를 사용하므로 그 version은 not in-place이다.
• 나쁜 표현: QuickSort는 평균적으로 빠르다. 좋은 표현: randomized pivot 선택에 대한 expected Laufzeit는 \(\Theta(n \log n)\)Θ(n log n)이지만 worst case는 \(\Theta(n^{2})\)Θ(n²)이다.
• 나쁜 표현: stable은 정렬이 안정적이라는 뜻이다. 좋은 표현: stable(stabil)은 equal keys를 가진 원소들의 relative order가 입력과 출력에서 보존된다는 뜻이다.
• 나쁜 표현: decision tree에는 n개의 leaf가 필요하다. 좋은 표현: n distinct keys의 possible input permutations가 n!개이므로 correct sorter에는 적어도 n!개의 distinguishable leaves가 필요하다.
• 나쁜 표현: comparison 한 번은 값을 하나 찾는다. 좋은 표현: comparison 한 번은 yes/no result 하나를 주며 decision tree에서 binary branch 하나에 해당한다.
• 나쁜 표현: CountingSort는 \(O(n)\)O(n)이다. 좋은 표현: key range가 0..K이면 CountingSort는 \(\Theta(n+K)\)Θ(n+K)이고, K가 제한될 때 linear처럼 볼 수 있다.
• 나쁜 표현: RadixSort에서 r을 키우면 무조건 좋다. 좋은 표현: r을 키우면 pass 수 b/r은 줄지만 bucket 수 \(2^{r}\)2^r이 증가하므로 trade-off가 있다.
• 나쁜 표현: lower bound proof는 Stirling formula를 외우면 된다. 좋은 표현: 핵심은 \(2^{m} \text{leaf} \text{capacity}\)2ᵐ leaf capacity와 n! permutation demand이고, \(\log(n!) = \Omega(n \log n)\)log(n!) = Ω(n log n)은 뒤쪽 절반 항으로도 설명할 수 있다.

36. 장 전체를 하나의 이야기로 묶기

이 장의 흐름을 한 문단으로 다시 말하면 다음과 같습니다. 정렬은 key를 기준으로 객체를 재배열하는 문제이고, satellite data 때문에 stability가 의미를 가질 수 있습니다. comparison-based sorting은 순서 정보를 비교로만 얻으므로 실행을 yes/no decision tree로 표현할 수 있습니다. m번 비교하는 tree는 최대 \(2^{m} \text{leaves}\)2ᵐ leaves만 가지지만, n distinct keys에는 n! input permutations가 있으므로 correct sorter는 \(2^{m} \ge n!\)2ᵐ ≥ n!을 만족해야 합니다. 그래서 worst-case comparisons는 \(\Omega(n \log n)\)Ω(n log n)입니다. MergeSort와 HeapSort는 이 lower bound에 맞는 \(\Theta(n \log n)\)Θ(n log n) comparison sorts이고, InsertionSort는 특정 입력에서는 빠르지만 worst case는 \(\Theta(n^{2})\)Θ(n²)입니다. QuickSort는 randomized expected와 worst를 분리해야 합니다. CountingSort와 RadixSort는 key range 또는 digit/bucket 정보를 쓰는 다른 모델이라 lower bound의 반례가 아니라 전제가 다른 알고리즘입니다. 마지막으로 stable, in-place, runtime, model은 서로 다른 축이므로 알고리즘을 평가할 때 네 칸 표로 나누어 말해야 합니다.

핵심 학습 항목 (37. active recall answer bank)

다음 항목은 질문으로도 쓰고, 짧은 모범 답안으로도 쓸 수 있는 구술 암기 뼈대입니다. 각 항목을 손으로 가리고 앞부분만 보고 답해 보세요.

• 정렬의 사후조건은 키 순서 조건만으로 끝나지 않습니다. 출력 배열은 입력과 같은 객체들을 같은 개수로 가져야 하므로 순열 또는 다중집합 보존도 필요합니다.
• key와 satellite data의 차이는 정렬 기준과 함께 운반되는 나머지 정보의 차이입니다. 같은 key가 여러 개이면 satellite data의 상대 순서 때문에 stability가 관찰됩니다.
• total order가 필요한 이유는 어떤 두 key를 비교해도 <= 관계로 순서를 판단할 수 있어야 sorting problem이 명확해지기 때문입니다.
• comparison-based model에서는 알고리즘이 key의 digit, bit pattern, bounded range를 직접 쓰지 않고 comparison result만 order information으로 사용합니다.
• decision tree는 특정 구현 언어의 tree 자료구조가 아니라 가능한 실행 경로를 나타내는 분석 도구입니다.
• internal node가 comparison이라는 말은 그 node에서 아직 구분되지 않은 입력들에 대해 다음으로 묻는 질문이 \(A[i] \le A[j]\)A[i] ≤ A[j]? 같은 비교라는 뜻입니다.
• edge가 yes/no라는 말은 비교 결과 하나가 가능한 입력 집합을 두 부분으로 나눈다는 뜻입니다.
• leaf가 distinguished case라는 말은 그 leaf에 도착한 입력들에 대해 알고리즘이 더 이상 비교하지 않고 하나의 최종 결정을 내린다는 뜻입니다.
• worst-case m comparisons는 모든 root-to-leaf path 길이가 m 이하이거나 가장 긴 path가 m이라는 뜻입니다.
• \(\text{at} \text{most} 2^{m} \text{leaves}\)at most 2ᵐ leaves는 binary branching의 capacity입니다. 실제 알고리즘은 덜 꽉 찬 tree를 가질 수 있습니다.
• n! permutations는 n개의 서로 다른 key를 배열하는 모든 가능한 입력 순서를 셉니다. key가 중복되면 안정성 논의가 생기지만 lower bound proof는 distinct keys로 충분합니다.
• \(2^{m} \ge n!\)2ᵐ ≥ n!는 알고리즘이 충분히 많은 서로 다른 경우를 구분할 수 있어야 한다는 necessary condition입니다.
• \(\log_{2}(n!) = \Omega(n \log n)\)log2(n!) = Ω(n log n)은 Stirling formula 없이도 뒤쪽 n/2개 항이 모두 n/2 이상이라는 lower estimate로 설명할 수 있습니다.
• \(\Omega(n \log n)\)Ω(n log n)은 lower bound입니다. 어떤 알고리즘이 정확히 그 시간이라는 뜻은 아니며, InsertionSort처럼 더 느린 comparison sort도 있습니다.
• MergeSort의 \(\Theta(n \log n)\)Θ(n log n)은 recurrence analysis에서 나온 upper bound이고, lower bound와 합쳐져 comparison model에서 optimal하다고 말할 수 있습니다.
• HeapSort도 comparison-based이며 worst-case \(\Theta(n \log n)\)Θ(n log n)을 보장하지만 일반적인 구현은 stable하지 않습니다.
• QuickSort의 장점은 실제 성능과 expected behavior이지만, proof answer에서는 \(\text{worst}-\text{case} \Theta(n^{2})\)worst-case Θ(n²)을 반드시 기억해야 합니다.
• CountingSort는 count array index를 쓰므로 key range K가 runtime과 memory에 직접 들어갑니다.
• RadixSort는 digit pass를 반복하므로 digit 수 d가 runtime에 들어가고, digit alphabet 또는 bucket 수 D도 들어갑니다.
• LSD RadixSort의 stable pass는 낮은 자리 정보를 보존하기 위한 correctness 조건입니다.
• stable은 같은 key의 상대 순서 보존이고, in-place는 extra memory 제한입니다. 둘을 연결해 추론하면 안 됩니다.
• MC에서 'always', 'all', 'worst', 'expected', 'linear' 같은 단어는 범위를 넓히거나 좁히므로 먼저 밑줄을 그어야 합니다.
• 답안을 독일어 용어와 연결하면 Sortieren, Schluesselwert, Satellitendaten, vergleichsbasiertes Sortieren, untere Schranke, Entscheidungsbaum, stabil, Laufzeit를 적절히 붙이면 됩니다.
• 최종 한 줄 요약은 다음과 같습니다. comparison-only questions form a binary decision tree, but correct sorting must distinguish n! permutations, so worst-case comparisons are \(\Omega(n \log n)\)Ω(n log n).

38. 알고리즘별 oral follow-up 방어 문장

examiner가 특정 알고리즘을 하나씩 물을 때 바로 붙일 수 있는 방어 문장입니다. 이름, 모델, runtime case, stability/in-place 중 빠진 축을 채우는 연습을 하세요.

• InsertionSort: comparison-based이며 sorted prefix에 key를 삽입합니다. best case는 이미 정렬된 입력에서 \(\Theta(n)\)Θ(n), reverse input worst case는 shift 합 때문에 \(\Theta(n^{2})\)Θ(n²)입니다.
• InsertionSort stability: equal keys를 지나쳐 이동시키지 않는 조건, 예를 들어 strict greater-than일 때만 shift하면 stable합니다.
• InsertionSort in-place: array 안에서 shift하고 key 변수 정도만 쓰므로 일반적으로 in-place로 봅니다.
• MergeSort: comparison-based divide and conquer입니다. 두 half를 재귀 정렬하고 linear merge를 하므로 \(T(n)=2T(n/2)+\Theta(n)=\Theta(n \log n)\)T(n)=2T(n/2)+Θ(n)=Θ(n log n)입니다.
• MergeSort stability: merge tie에서 left half 원소를 먼저 output하면 equal-key order가 보존됩니다.
• MergeSort memory: lecture merge는 temporary array B를 사용하므로 그 version은 not in-place입니다.
• QuickSort: comparison-based partition algorithm입니다. pivot 기준으로 나누지만 partition만으로 각 side가 정렬되는 것은 아닙니다.
• QuickSort worst case: pivot이 계속 extreme value이면 subproblem sizes가 0과 n-1로 갈라져 \(\Theta(n^{2})\)Θ(n²)이 됩니다.
• QuickSort randomized expected: random pivot은 expected recursion balance를 좋게 만들지만 absolute worst-case guarantee를 n log n으로 바꾸지는 않습니다.
• HeapSort: comparison-based이며 heap order를 이용합니다. worst-case \(\Theta(n \log n)\)Θ(n log n), 일반 array heap version은 in-place 장점이 있지만 stable하지 않습니다.
• CountingSort: bounded integer keys 0..K 같은 전제가 있어야 합니다. runtime은 \(\Theta(n+K)\)Θ(n+K)이고 K가 크면 linear가 아닙니다.
• CountingSort stability: prefix counts와 output fill direction을 올바르게 쓰면 stable하게 만들 수 있지만, 핵심 전제는 key range입니다.
• RadixSort: digit representation을 사용해 여러 stable bucket/counting passes를 수행합니다. comparison lower bound 밖에 있습니다.
• RadixSort runtime: d digits, digit alphabet D이면 \(O(d(n+D))\)O(d(n+D))입니다. d와 D가 상수일 때만 \(O(n)\)O(n)처럼 요약할 수 있습니다.
• RadixSort bit grouping: r bits per digit이면 buckets는 \(2^{r}, \text{passes}\)2^r, passes는 b/r입니다. 이 둘을 곱해 \(O((b/r)(n+2^{r}))\)O((b/r)(n+2^r))입니다.
• Lower bound relation: MergeSort/HeapSort는 lower bound에 맞는 좋은 comparison sorts이고, Counting/Radix는 model을 바꾸어 다른 조건에서 빠른 sorts입니다.
• Stability relation: MergeSort와 InsertionSort는 stable하게 만들 수 있지만 QuickSort와 HeapSort는 일반 구현에서 stable하지 않다고 보는 것이 안전합니다.
• In-place relation: InsertionSort와 HeapSort는 보통 in-place, lecture MergeSort와 Counting/Radix는 추가 배열 때문에 not in-place로 보는 것이 안전합니다.

핵심 학습 항목 (39. source-grounded study path)

자료를 다시 볼 때는 PDF 전체를 처음부터 읽기보다 아래 순서로 확인하면 좋습니다. 각 source에서 무엇을 확인해야 하는지 목적을 정하고 들어가세요.

• Vorlesung 02의 sorting problem 초반부에서는 key, satellite data, array representation, total order를 확인합니다. 이 부분은 정의 문장을 만드는 데 필요합니다.
• InsertionSort slides에서는 correctness와 stability 언급, 그리고 worst-case line count나 shift count를 확인합니다. reverse input에서 왜 quadratic인지 말할 수 있어야 합니다.
• MergeSort slides에서는 split, recursive calls, merge with temporary array B, recurrence shape를 확인합니다. stable tie rule과 in-place caveat를 따로 적어 둡니다.
• QuickSort 부분을 볼 때는 partition이 무엇을 보장하고 무엇을 보장하지 않는지 분리합니다. pivot choice가 recursion tree shape를 만든다는 점을 표시합니다.
• comparison lower bound slides에서는 vergleichsbasiertes Sortieren 정의, \(\text{decision} \text{tree}, 2^{m} \text{answer} \text{sequences}, n! \text{permutations}, \Omega(n \log n)\)decision tree, 2ᵐ answer sequences, n! permutations, Ω(n log n)결론을 한 줄씩 연결합니다.
• RadixSort slides에서는 LSD order, buckets, \(O(d(n+D))\)O(d(n+D)), stable pass intuition을 확인합니다. lower bound 반례가 아니라 model difference라는 문장을 옆에 적습니다.
• Sheet03에서는 MergeSort/QuickSort를 손으로 실행하는 감각을 확인합니다. 그림을 그릴 때 partial order와 partition/merge 단계가 섞이지 않도록 주의합니다.
• Sheet04에서는 lower bound와 RadixSort formula를 확인합니다. 특히 \(O((b/r)(n+2^{r}))\)O((b/r)(n+2^r))에서 \(b, r, 2^{r}, b/r\)b, r, 2^r, b/r이 각각 무엇인지 독일어/영어 term과 함께 말해 봅니다.
• exam memory의 sorting task는 손 실행과 invariant proof가 섞일 수 있음을 보여 줍니다. 정렬 알고리즘 실행 문제에서도 correctness vocabulary가 배경으로 필요합니다.
• Obsidian export에서는 이 페이지의 Full Lecture Sections, Worked Examples, MC Checklist를 복습하고, 틀린 항목은 \(\text{weakness}_{\text{log}}\)weakness(log)에 \(\text{topic}=\text{Sorting}\quad\text{and}\quad \text{lower} \text{bounds}\)topic=Sorting and lower bounds로 남기면 다음 Study Hub rebuild에서 추적할 수 있습니다.

40. mini exam drill: 판단과 한 줄 근거

아래 drill은 실제 MC와 oral 사이 형태입니다. 각 항목의 핵심은 정답 자체보다 한 줄 근거입니다. 근거를 말하지 못하면 운으로 맞힌 것입니다.

• 판단: 'A stable sorting algorithm always uses extra memory.' 정답: false. 근거: stability는 equal-key relative order이고 memory usage와 독립입니다. InsertionSort는 stable하고 in-place로 구현할 수 있습니다.
• 판단: 'A not-in-place algorithm can be stable.' 정답: true. 근거: lecture MergeSort는 temporary array B를 쓰지만 left-first merge tie rule로 stable하게 만들 수 있습니다.
• 판단: 'If an algorithm has best case \(\Theta(n)\)Θ(n), it contradicts the sorting lower bound.' 정답: false. 근거: lower bound는 worst-case comparisons에 대한 statement입니다.
• 판단: 'A comparison sort with worst-case \(\Theta(n \log n)\)Θ(n log n) is asymptotically optimal in the comparison model.' 정답: true. 근거: comparison lower bound가 \(\Omega(n \log n)\)Ω(n log n)이기 때문입니다.
• 판단: 'If a sorting algorithm reads key bits directly, the decision-tree proof applies unchanged.' 정답: false. 근거: proof는 order information이 comparisons에서만 나온다는 assumption을 씁니다.
• 판단: 'Decision-tree lower bound assumes all keys are distinct.' 정답: proof에서는 distinct keys case만 봐도 충분합니다. 그 restricted case에서 이미 n! permutations가 필요합니다.
• 판단: 'For \(n=5,\)n=5, four comparisons are enough by information capacity.' 정답: false. 근거: \(2^{4}=16\)2⁴=16이고 \(5\ne 120\)5!=120이므로 capacity가 부족합니다.
• 판단: 'For \(n=5,\)n=5, seven comparisons are guaranteed sufficient because \(2^{7}\)2⁷ >= 5!.' 정답: false. 근거: capacity necessary condition을 만족할 뿐 실제 algorithm existence를 보장하는 충분조건은 아닙니다.
• 판단: 'QuickSort partition makes every left element <= every right element after one partition.' 정답: pivot 기준으로는 맞지만, left 내부와 right 내부가 sorted라는 뜻은 아닙니다.
• 판단: 'QuickSort worst case happens only on sorted input.' 정답: false. 근거: pivot rule에 따라 sorted input이 worst가 될 수 있지만 핵심은 repeated extreme pivot입니다.
• 판단: 'MergeSort runtime depends on input order.' 정답: standard MergeSort에서는 splitting and merging structure 때문에 모든 입력에서 \(\Theta(n \log n)\)Θ(n log n)으로 봅니다.
• 판단: 'InsertionSort runtime depends strongly on input order.' 정답: true. 근거: while loop shift count가 inversion 또는 disorder 정도에 따라 달라집니다.
• 판단: 'CountingSort is comparison-based because it eventually orders keys.' 정답: false. 근거: ordering을 count array index와 key range로 얻습니다.
• 판단: 'RadixSort needs stable subroutine in LSD form.' 정답: true. 근거: 낮은 자리 digit order를 높은 자리 pass가 보존해야 합니다.
• 판단: '\(O(d(n+D))\)O(d(n+D)) becomes \(O(n)\)O(n) if d and D are constants.' 정답: true. 근거: 상수 factor와 상수 additive bucket scan은 asymptotic에서 흡수됩니다.
• 판단: '\(O((b/r)(n+2^{r}))\)O((b/r)(n+2^r))에서 r을 두 배로 하면 항상 runtime이 줄어든다.' 정답: false. 근거: pass 수는 줄지만 \(\text{bucket} \text{term} 2^{r}\)bucket term 2^r이 커집니다.
• 판단: 'n! in the proof counts possible comparison outcomes.' 정답: false. 근거: possible comparison outcomes capacity는 \(2^{m}\)2ᵐ이고, n!은 input permutations입니다.
• 판단: 'A leaf can represent more than one input if those inputs do not need to be distinguished.' 정답: 일반 decision tree에서 가능하지만, distinct-key correct sorting lower-bound proof에서는 n! permutations를 충분히 분리해야 한다고 argument합니다.
• 판단: 'The lower-bound proof is an adversarial argument.' 정답: 넓게 보면 worst-case information argument입니다. adversary라는 단어를 써도 되지만 decision tree capacity로 설명하는 편이 이 페이지의 source에 가깝습니다.
• 판단: '\(\Theta(n \log n)\)Θ(n log n) lower bound means every input takes n log n comparisons.' 정답: false. 근거: worst-case lower bound는 어떤 입력에서 그만큼 필요함을 말하며 모든 입력별 cost statement가 아닙니다.
• 판단: 'Stable output for [3a, 3b, 2] is [2, 3a, 3b].' 정답: true. 근거: key 3끼리 입력의 a before b order가 유지됩니다.
• 판단: 'Sorted output for [3a, 3b, 2] can be [2, 3b, 3a].' 정답: key만 보면 sorted이지만 stable은 아닙니다. 문제에서 stable을 요구하는지 확인해야 합니다.
• 판단: 'If all keys are unique, stability is unobservable.' 정답: true in effect. 근거: equal-key pair가 없으므로 relative order preservation 조건이 드러나지 않습니다.
• 판단: 'Satellite data must move together with the key.' 정답: true. 근거: 정렬 대상은 key만이 아니라 key를 가진 object입니다.
• 판단: 'A sorting proof only needs to show the output is nondecreasing.' 정답: false. 근거: 원소 보존 또는 permutation condition도 필요합니다.
• 판단: 'MergeSort recurrence alone proves stability.' 정답: false. 근거: recurrence는 runtime이고 stability는 merge tie behavior에 관한 correctness property입니다.
• 판단: 'QuickSort being in-place implies it is stable.' 정답: false. 근거: partition swaps can change equal-key relative order.
• 판단: 'HeapSort being comparison-based means it cannot beat \(\Omega(n \log n)\)Ω(n log n) worst-case comparisons.' 정답: true. 근거: lower bound applies to all correct comparison sorts.
• 판단: 'CountingSort memory is independent of key range.' 정답: false. 근거: count array size depends on K.
• 판단: 'RadixSort pass count is independent of key length.' 정답: false. 근거: digit count d or b/r pass count depends on representation length.
• 판단: 'The phrase untere Schranke should make you think Omega.' 정답: true. 근거: lower bound is Omega-style statement, while tight bound is Theta.
• 판단: 'The phrase Laufzeit alone is enough for QuickSort.' 정답: false. 근거: must specify worst, expected, average, or best case.
• 판단: 'The phrase vergleichsbasiertes Sortieren is the key condition for decision-tree lower bound.' 정답: true. 근거: it fixes the information model to comparisons.
• 판단: 'If an MC option says RadixSort \(O(n)\)O(n) without d,D conditions, mark it suspicious.' 정답: true. 근거: source formula includes digit and bucket terms.
• 판단: 'If an MC option says MergeSort is not stable, it may depend on implementation.' 정답: true. 근거: left-first tie merge is stable, but a different tie policy can break stability.
• 판단: 'The safest exam comparison table has runtime, stable, in-place, model/precondition columns.' 정답: true. 근거: most false statements omit one of these columns.

핵심 학습 항목 (41. final lecture recap in Korean)

정렬과 lower bound를 처음 배우는 학생에게 가장 중요한 변화는 '알고리즘 이름 중심'에서 '모델과 조건 중심'으로 넘어가는 것입니다. InsertionSort, MergeSort, QuickSort, HeapSort, CountingSort, RadixSort는 모두 정렬이라는 같은 목표를 향하지만, 사용하는 정보와 보장하는 성질이 다릅니다. comparison-based 알고리즘은 비교 결과만으로 순서 정보를 얻기 때문에 decision tree로 분석되고, 이때 binary answer capacity 때문에 \(\Omega(n \log n)\)Ω(n log n) lower bound가 생깁니다. non-comparison 알고리즘은 그 bound를 무시하는 것이 아니라 key range나 digit representation 같은 추가 구조를 사용합니다. 따라서 시험에서 좋은 답안은 '무엇이 빠르다'가 아니라 '어떤 모델에서, 어떤 case에서, 어떤 전제로, 어떤 성질을 보장한다'라고 말하는 답안입니다. 이 기준으로 보면 lower bound proof, algorithm table, stability example, RadixSort caveat가 하나의 이야기로 연결됩니다.

핵심 학습 항목 (42. common wrong answers and repairs)

마지막으로 실제 답안에서 자주 보이는 틀린 문장을 시험용 문장으로 고쳐 봅니다. 이 부분은 암기보다 표현 교정에 가깝습니다.

• 틀린 답: comparison sort는 n개의 원소를 비교하므로 n log n이다. 수정: comparison sort lower bound는 n! possible permutations를 binary comparisons로 구분해야 하므로 \(\log_{2}(n!) = \Omega(n \log n) \text{comparisons}\)log2(n!) = Ω(n log n) comparisons가 필요하다는 정보량 argument입니다.
• 틀린 답: leaf는 정렬된 배열 하나이다. 수정: leaf는 comparison history가 끝난 final decision case입니다. proof에서는 distinct input permutations를 충분히 구분해야 하므로 최소 n! leaves가 필요하다고 말합니다.
• 틀린 답: RadixSort는 비교를 안 하니까 항상 더 좋다. 수정: RadixSort는 digit representation, digit count d, bucket count D, stable passes, extra memory 조건이 맞을 때 빠릅니다.
• 틀린 답: CountingSort는 정렬 알고리즘이 아니므로 lower bound와 무관하다. 수정: CountingSort도 sorting algorithm이지만 comparison-based가 아니라 bounded integer key model을 사용합니다.
• 틀린 답: MergeSort는 lower bound 때문에 \(\Theta(n \log n)\)Θ(n log n)이다. 수정: MergeSort의 upper bound는 recurrence analysis로 보이고, lower bound는 comparison model에서 그보다 asymptotically 더 빠른 comparison sort가 없음을 말합니다.
• 틀린 답: QuickSort는 pivot만 잘 고르면 worst도 n log n이다. 수정: 특정 pivot strategy나 randomized expected를 말할 수 있지만 일반 QuickSort의 worst-case는 bad pivot sequence 때문에 \(\Theta(n^{2})\)Θ(n²)입니다.
• 틀린 답: stable은 정렬 결과가 바뀌지 않는다는 뜻이다. 수정: stable은 equal keys를 가진 원소들의 relative input order가 output에서도 보존된다는 뜻입니다.
• 틀린 답: in-place는 recursion을 쓰지 않는다는 뜻이다. 수정: in-place는 auxiliary storage가 작다는 뜻이고, recursion stack을 어떻게 계산할지는 구현/분석 convention을 확인해야 합니다.
• 틀린 답: InsertionSort가 best \(\Theta(n)\)Θ(n)이므로 comparison sorting lower bound가 틀렸다. 수정: lower bound는 worst-case statement이고, best-case input 하나가 쉬운 것은 모순이 아닙니다.
• 틀린 답: n!은 n개 원소의 출력 위치 수다. 수정: n!은 서로 다른 n개 key가 입력으로 들어올 수 있는 permutation 수입니다.
• 틀린 답: \(2^{m}\)2ᵐ은 comparisons 수다. 수정: m이 comparisons 수이고, \(2^{m}\)2ᵐ은 그 comparisons로 만들 수 있는 최대 answer sequences 또는 leaves 수입니다.
• 틀린 답: \(\log(n!) = n \log n\)log(n!) = n log n은 정확한 등식이다. 수정: asymptotically \(\Theta(n \log n)\)Θ(n log n)이고 lower-bound proof에는 \(\Omega(n \log n)\)Ω(n log n)이면 충분합니다.
• 틀린 답: Sheet04 formula에서 \(2^{r}\)2^r은 pass 수다. 수정: \(2^{r}\)2^r은 r-bit digit이 가질 수 있는 bucket 수이고, pass 수는 b/r입니다.
• 틀린 답: b/r은 bucket 수다. 수정: b-bit key를 r bits씩 나누므로 b/r은 처리해야 할 digit pass 수입니다.
• 틀린 답: d는 데이터 개수다. 수정: RadixSort formula \(O(d(n+D))\)O(d(n+D))에서 d는 digit 수이고 n이 원소 수입니다.
• 틀린 답: D는 입력 배열 길이다. 수정: D는 digit alphabet size 또는 bucket 수입니다.
• 틀린 답: comparison lower bound가 있으면 non-comparison sorting은 불가능하다. 수정: non-comparison sorting은 다른 operations와 stronger input assumptions를 사용하므로 가능합니다.
• 틀린 답: stable sorting은 항상 unique output을 만든다. 수정: stable은 equal-key order를 제한하지만, key와 객체 구분, 입력 중복 구조에 따라 표현을 정확히 해야 합니다.
• 틀린 답: lower bound proof는 implementation detail이다. 수정: decision tree proof는 모든 comparison-based algorithms를 포괄하는 model-level proof입니다.
• 틀린 답: 정렬 표는 runtime만 알면 된다. 수정: AUD exam에서는 runtime, stable, in-place, model/precondition, case distinction을 함께 묻는 문장이 많습니다.

핵심 학습 항목 (43. final rapid-fire checklist)

시험 직전에는 아래 checklist를 소리 내어 읽으면서 각 항목에 예시 하나를 붙여 보세요. 예시가 붙지 않으면 아직 개념이 추상적으로만 남아 있다는 뜻입니다.

• Sortieren: key 기준으로 객체들을 재배열하고, 객체 자체와 satellite data는 함께 이동해야 합니다. 예시는 학생 기록을 점수 key로 정렬하는 상황입니다.
• Schluesselwert: 비교되는 기준 값입니다. 같은 key가 있을 수 있으므로 정렬 결과의 안정성 문제가 생깁니다.
• Satellitendaten: key가 아닌 나머지 정보입니다. stable sorting이 필요한 이유를 보여 주는 데 좋습니다.
• Vergleichsbasiertes Sortieren: order information이 comparisons에서만 나오는 모델입니다. lower bound proof의 출발점입니다.
• Entscheidungsbaum: 모든 possible comparison histories를 tree로 나타낸 것입니다. root-to-leaf path가 한 실행입니다.
• Untere Schranke: 어떤 모델 안에서 그보다 더 적게는 보장할 수 없다는 아래쪽 제한입니다. 여기서는 \(\Omega(n \log n)\)Ω(n log n)입니다.
• Worst-case comparisons: 모든 입력 중 가장 많이 비교하는 경우를 봅니다. best-case와 섞지 마세요.
• InsertionSort: 거의 정렬된 입력에서 좋지만 reverse input에서 quadratic입니다. stable/in-place 예시로 쓰기 좋습니다.
• MergeSort: recurrence와 lower bound를 연결하는 핵심 알고리즘입니다. stable tie rule과 temporary array B를 함께 기억합니다.
• QuickSort: pivot quality가 핵심입니다. randomized expected와 worst-case를 절대 같은 문장으로 뭉개지 않습니다.
• CountingSort: key range K가 runtime과 memory에 들어갑니다. K 조건 없이 \(O(n)\)O(n)이라고 말하지 않습니다.
• RadixSort: digit 수 d와 bucket 수 D가 runtime에 들어갑니다. LSD 방식에서는 stable digit passes가 correctness 조건입니다.
• Bit grouping: \(b-\text{bit} \text{key}, r-\text{bit} \text{digit}, 2^{r} \text{buckets}, b/r \text{passes}\)b-bit key, r-bit digit, 2^r buckets, b/r passes를 한 번에 말합니다.
• Stable vs in-place: 하나는 equal-key order, 하나는 extra memory입니다. 두 성질은 서로 독립입니다.
• 최종 증명 문장: m번 비교로 만들 수 있는 잎은 최대 2ᵐ개이고 올바른 정렬은 최소 n!개의 순열을 구분해야 하므로 \(m \ge \log_{2}(n!) = \Omega(n \log n)\)m ≥ log₂(n!) = Ω(n log n)입니다.

44. 시험 직전 5분 능동 회상

마지막 5분에는 긴 설명보다 정확한 한 줄을 빠르게 꺼내는 능력이 중요합니다. 각 회상 질문의 앞부분만 보고 뒷부분을 말해 보세요.

• Q: lower bound proof의 첫 가정은? A: n distinct keys를 정렬하는 arbitrary correct comparison-based sorting algorithm을 잡습니다.
• Q: comparison result 하나가 주는 정보는? A: yes/no 한 bit에 가까운 binary branch 하나입니다.
• Q: decision tree depth와 worst-case comparisons의 관계는? A: 가장 긴 root-to-leaf path 길이가 worst-case comparison count입니다.
• Q: leaf capacity formula는? A: \(\text{depth} m \text{binary} \text{tree} \text{has} \text{at} \text{most} 2^{m} \text{leaves}\)depth m binary tree has at most 2ᵐ leaves입니다.
• Q: correctness demand formula는? A: at least n! distinguishable input permutations for n distinct keys입니다.
• Q: inequality chain은? A: \(2^{m} \ge n!, \text{so} m \ge \log_{2}(n!),\quad\text{and}\quad \log_{2}(n!) = \Omega(n \log n)\)2ᵐ ≥ n!, so m ≥ log2(n!), and log2(n!) = Ω(n log n)입니다.
• Q: RadixSort caveat 한 줄은? A: digit/bucket access를 쓰는 non-comparison model이므로 comparison lower bound의 직접 대상이 아닙니다.
• Q: CountingSort caveat 한 줄은? A: bounded integer key range K가 있어야 하며 runtime은 \(\Theta(n+K)\)Θ(n+K)입니다.
• Q: MergeSort caveat 한 줄은? A: \(\Theta(n \log n)\)Θ(n log n)이고 stable tie rule이 가능하지만 lecture merge uses temporary array B입니다.
• Q: QuickSort caveat 한 줄은? A: randomized expected \(\Theta(n \log n)\)Θ(n log n)과 \(\text{worst} \Theta(n^{2})\)worst Θ(n²)을 분리합니다.
• Q: InsertionSort caveat 한 줄은? A: \(\text{best} \Theta(n), \text{worst} \Theta(n^{2}), \text{stable}\quad\text{and}\quad \text{in}-\text{place} \text{implementation} \text{is} \text{possible}\)best Θ(n), worst Θ(n²), stable and in-place implementation is possible입니다.
• Q: stable definition 한 줄은? A: equal-key elements keep their relative input order in the output입니다.
• Q: in-place definition 한 줄은? A: algorithm uses only small auxiliary storage beyond the input array, depending on convention입니다.
• Q: Sheet04 formula 한 줄은? A: \(b-\text{bit} \text{keys} \text{grouped} \text{by} r \text{bits} \text{give} b/r \text{passes}\quad\text{and}\quad 2^{r} \text{buckets}, \text{so} O((b/r)(n+2^{r})).\)b-bit keys grouped by r bits give b/r passes and 2^r buckets, so O((b/r)(n+2^r)).
• Q: common MC rescue strategy는? A: add model, case, precondition, and property axis before deciding true or false.
• Q: source anchor for lower bound는? A: Vorlesung 02 comparison-based sorting and decision-tree lower-bound pages.
• Q: source anchor for RadixSort는? A: Vorlesung 02 RadixSort pages and Sheet04 bit grouping task.
• Q: source anchor for MergeSort recurrence는? A: Vorlesung 02 MergeSort section and Sheet03 divide-and-conquer practice.
• Q: oral final sentence는? A: The lower bound is tight for comparison sorting because MergeSort and HeapSort achieve \(\Theta(n \log n)\)Θ(n log n).
• 질문: 피해야 할 표현은? 답: 비교 기반·최악 비교 횟수라는 범위를 붙이지 않은 채 모든 정렬 알고리즘에 \(\Omega(n \log n)\)Ω(n log n)이 필요하다고 말하면 안 됩니다.