부분 배열과 양끝 포함 구간(inclusive range)
퀵 정렬(QuickSort)은 전체 배열 중 왼쪽 경계부터 오른쪽 경계까지의 구간만 다룹니다. 두 끝 인덱스를 모두 포함하므로 길이는 right-left+1입니다.
아주 작은 예: [5,2,8,1]의 [1..2]는 [2,8]입니다.
3. Sortieralgorithmen (10 Punkte)
3.1(b) · 퀵 정렬(QuickSort) — 첫 기준값과 호어 분할을 끝까지 추적하기
선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.
- 용어: 기호와 전제
- 직관: 비유와 작은 예
- 풀이: 실제 상태 변화
- 확인: 검산과 자가점검
자료의 성격과 정확성 경계
시험 문언과 배열, 배점, MinSort 빈칸은 SoSe 2025 기억 복기 자료에서 가져온 재구성(reconstructed)이며 공식 답안지가 아닙니다. Insertion Sort와 Hoare QuickSort의 알고리즘 규칙은 SoSe 2026 현재 강의 슬라이드로 검증했고, invariant 증명 형식은 현재 연습문제와 풀이로 교차 확인했습니다. 따라서 QuickSort trace는 이 페이지에 명시한 ‘첫 원소 pivot + Hoare partition’ 규칙에서만 같은 모양이 됩니다.
문제를 읽기 전에 알아둘 기호와 용어
기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.
| 기호·용어 | 뜻 | 작은 예 |
|---|---|---|
| 항목 (A[i]) | 배열 A의 i번째 index에 저장된 값입니다. 이 페이지는 0부터 세므로 첫 칸은 A[0]입니다. | 초기 배열에서 \(A[0]=10, A[2]=2\)A[0]=10, A[2]=2 |
| 항목 (A[l..r]) | index l부터 r까지 양 끝을 포함하는 연속 부분 배열입니다. \(l>r\)l>r이면 empty range로 읽습니다. | \(A[0..2]=[10,7,2], A[0..-1]=\text{empty}\)A[0..2]=[10,7,2], A[0..-1]=empty |
| 키 | 정렬 순서를 결정하는 비교값이며 Insertion Sort에서는 이번에 왼쪽 prefix에 삽입할 값입니다. | \(j=3\)j=3이면 \(\text{key}=A[3]=3\)key=A[3]=3 |
| 항목 (swap(x,y)) | 두 위치의 값을 서로 교환하는 연산입니다. 값의 개수는 바뀌지 않으므로 multiset이 보존됩니다. | swap(10,4) 뒤 두 값의 자리만 바뀜 |
| 항목 (p, q) | Hoare partition에서 아직 분류되지 않은 가운데 구간을 양쪽에서 좁히는 두 pointer입니다. | p는 ≥pivot에서, q는 ≤pivot에서 멈춤 |
| 항목 (I(i)) | 반복문의 정해진 시점마다 참이어야 하는 loop invariant를 index i로 표시한 것입니다. | MinSort의 I(i): 앞 i칸은 가장 작은 i개 |
\(\Theta(f(n))\)Θ(f(n)) | 입력 크기 n이 커질 때 실행량이 f(n)과 같은 차수로 증가한다는 점근적 표기입니다. | \(\text{Insertion} \text{Sort} \text{worst} \text{case} \Theta(n^{2})\)Insertion Sort worst case Θ(n²) |
먼저 문제의 정체를 줄글로 이해하기
QuickSort는 pivot 하나를 기준으로 작은 값 영역과 큰 값 영역을 만든 뒤 두 영역을 재귀적으로 정렬합니다. 핵심 작업은 merge가 아니라 partition에 있습니다.
QuickSort에는 여러 올바른 partition 방식이 있으므로 trace는 알고리즘 정의에 따라 달라집니다. 여기서는 현재 강의 pp.103-124의 방식, 즉 첫 원소를 pivot으로 선택하고 p는 왼쪽에서 ≥pivot을, q는 오른쪽에서 ≤pivot을 찾는 Hoare partition을 사용합니다.
partition이 반환한 q에서 pivot이 반드시 최종 위치에 있는 것은 아닙니다. 보장되는 것은 \(A[\text{left}..q] \le_{p} \text{ivot}, A[q+1..\text{right}]\ge \text{pivot}\)A[left..q]≤pivot, A[q+1..right]≥pivot이며 재귀 범위도 [left..q]와 [q+1..right]입니다.
필요한 개념을 깊게 배우기
0단계 · 분할 정복(Divide and Conquer)
Divide는 partition으로 두 부분 배열을 만들고, Conquer는 각 부분에 QuickSort를 재귀 호출하며, Combine은 별도 작업 없이 두 정렬 부분을 이어 보는 것입니다.
base case는 \(\text{left}\ge \text{right}\)left≥right인 길이 0 또는 1의 구간입니다. 이 구간은 이미 정렬되어 재귀 호출이 즉시 끝납니다.
수식으로 정확히 쓰기
핵심 규칙\operatorname{QuickSort}(A,\mathrm{left},q)
핵심 규칙\operatorname{QuickSort}(A,q+1,\mathrm{right})
1단계 · 호어 분할(Hoare partition)의 두 포인터
p는 왼쪽에서 출발해 pivot 이상인 첫 값을 찾고, q는 오른쪽에서 출발해 pivot 이하인 첫 값을 찾습니다. \(p<q\)p<q이면 두 값은 서로 잘못된 편에 있으므로 swap합니다.
p와 q가 만나거나 교차하면 q를 반환합니다. 매 반복에서 두 pointer가 가까워지므로 종료합니다.
수식으로 정확히 쓰기
핵심 규칙\mathrm{pivot}=A[\mathrm{left}]
핵심 규칙p:\; A[p]\ge\mathrm{pivot}\text{ 에서 정지}
핵심 규칙q:\; A[q]\le\mathrm{pivot}\text{ 에서 정지}
2단계 · 분할 불변식(partition invariant)
각 반복의 같은 시점에서 p 왼쪽의 확정 영역은 pivot 이하이고 q 오른쪽의 확정 영역은 pivot 이상입니다. 가운데만 아직 분류되지 않았습니다.
swap은 잘못된 양쪽 원소를 올바른 쪽으로 보내 이 invariant를 확장합니다. 종료 시 미분류 영역이 사라져 두 partition 조건이 완성됩니다.
수식으로 정확히 쓰기
핵심 규칙\forall x\in A[\mathrm{left}{:}q]:\;x\le\mathrm{pivot}
핵심 규칙\forall x\in A[q+1{:}\mathrm{right}]:\;x\ge\mathrm{pivot}
3단계 · 실행시간과 기준값(pivot)
한 분할(partition)은 구간을 한 번 훑으므로 \(\Theta(m)\)Θ(m)입니다. 균형 분할이 계속되면 깊이 \(\Theta(\log n)\)Θ(log n), 층마다 \(\Theta(n)\)Θ(n)으로 전체 \(\Theta(n \log n)\)Θ(n log n)입니다.
첫 원소를 기준값으로 삼을 때 이미 정렬된 배열처럼 매번 1개만 떨어지면 \(\Theta(n^{2})\)Θ(n²)입니다. 무작위 기준값은 입력과 독립적으로 좋은 분할을 기대해 평균 \(\Theta(n \log n)\)Θ(n log n)을 얻습니다.
수식으로 정확히 쓰기
\[T_{\text{최선/기대}}(n)=\Theta(n\log n)\]
T_{\text{최선/기대}}(n)=\Θ(n\log n)\[T_{\text{최악}}(n)=\Theta(n^{2})\]
T_{\text{최악}}(n)=\Θ(n²)이 소문제를 왜 배우나
QuickSort는 한 번에 정렬하는 알고리즘이 아니라 pivot으로 두 구간을 만들고 같은 문제를 재귀적으로 반복합니다. 시험에서는 partition 방식마다 trace가 달라지므로, 이름만 외우지 않고 pointer 규칙과 재귀 구간을 정확히 선언하는 능력이 핵심입니다.
- 첫 원소 pivot Hoare partition의 p·q 초기값, scan 정지 조건, swap 조건, 반환값을 순서대로 실행할 수 있습니다.
- partition 뒤 pivot이 최종 위치에 있다는 잘못된 가정을 피하고 [left..q], [q+1..right] 재귀 범위를 쓸 수 있습니다.
- 각 반환 q에서 두 partition 조건을 검산하고 재귀 호출이 길이 1에서 끝나는 이유를 설명할 수 있습니다.
풀이 전에 꼭 알아야 할 말
기준값(pivot)과 분할(partition)
기준값은 현재 구간을 나누는 값이고 분할은 기준값 이하 값이 왼쪽, 기준값 이상 값이 오른쪽에 있도록 재배치하는 과정입니다.
아주 작은 예: \(\text{pivot}=5\)
pivot=5이면 2는 왼쪽 조건, 8은 오른쪽 조건을 만족합니다.포인터(pointer) p와 q
p는 왼쪽에서 오른쪽으로, q는 오른쪽에서 왼쪽으로 움직이는 인덱스입니다. 둘이 멈춘 값이 반대편에 있어야 하면 맞바꿉니다(swap).
아주 작은 예: p가 9에서, q가 2에서 멈추면 9↔2로 교환합니다.
재귀와 종료 조건(base case)
함수가 더 작은 구간에 자기 자신을 호출하는 것을 재귀라 합니다. 길이 0 또는 1의 구간은 이미 정렬되어 더 나누지 않습니다.
아주 작은 예: quicksort(A,4,4)는 한 칸이라 즉시 끝납니다.
양쪽 검표원이 잘못 선 사람을 바꾸기
pivot 점수 10을 기준으로 왼쪽 검표원 p는 왼쪽 줄에서 10 이상인 사람을, 오른쪽 검표원 q는 오른쪽 줄에서 10 이하인 사람을 찾습니다. 두 사람이 아직 마주치지 않았다면 서로 반대편에 선 두 사람을 바꾸고, 검표원이 만나거나 지나치면 경계를 확정합니다.
기준 점수표
↔
\(\text{pivot}=A[\text{left}]\)
pivot=A[left]왼쪽 검표원
↔
p: \(A[p]\ge \text{pivot}\)
A[p]≥pivot에서 정지오른쪽 검표원
↔
q: \(A[q] \le_{p} \text{ivot}\)
A[q]≤pivot에서 정지검표원이 교차한 자리
↔
partition 경계 q
비유의 한계: 두 그룹은 partition 직후 내부까지 정렬된 것이 아닙니다. 또한 기준값 카드가 반드시 경계 q에 놓이는 방식도 아니므로, 재귀 호출로 양쪽 내부를 계속 정렬해야 합니다.
Hoare partition의 한 cycle
p<q이면 교환하고 반복, 아니면 q를 반환합니다.p와 q는 매 while cycle에서 적어도 한 칸 안쪽으로 움직입니다. \(p<q\)p<q일 때만 swap하고, \(p\ge q\)p≥q가 되면 마지막으로 계산된 q가 경계입니다.
먼저 작은 예제로 연습 · [5,8,2,7,1]을 한 번 partition
\(\text{left}=0, \text{right}=4, \text{pivot}=5, p=-1, q=5\)left=0, right=4, pivot=5, p=-1, q=5입니다. scan은 pointer를 먼저 한 칸 움직인 뒤 조건을 검사합니다.
p=0, q=4에서 정지\(A[0]=5\)A[0]=5는 pivot 이상이고 \(A[4]=1\)A[4]=1은 pivot 이하이므로 첫 정지점입니다.
\(p=0<q=4\)p=0<q=4이고 두 값은 각각 잘못된 쪽에 있으므로 위치를 바꿉니다.
p=1, q=2에서 정지왼쪽의 8은 5 이상, 오른쪽에서 찾은 2는 5 이하입니다.
\([1,8,2,7,5], p=1, q=2\)[1,8,2,7,5], p=1, q=2교환 뒤 다음 scan은 \(p=2, q=1\)p=2, q=1이 되어 \(p\ge q\)p≥q이므로 \(q=1\)q=1을 반환합니다.
[1,2 | 8,7,5], return q=1작은 예제의 결론: 왼쪽 [0..1]은 모두 5 이하이고 오른쪽 [2..4]는 모두 5 이상입니다. 두 구간 내부는 아직 정렬되지 않았으므로 각각 QuickSort를 호출합니다.
이제 실제 시험 문제에 연결
첫 P(0,8)에서 p와 q는 어디서 시작하나?
\(p=\text{left}-1=-1, q=\text{right}+1=9\)p=left-1=-1, q=right+1=9에서 시작합니다. 첫 scan 후 \(p=0\)p=0의 \(10, q=6\)10, q=6의 4에서 멈추고 \(p<q\)p<q이므로 두 값을 바꿉니다.
10↔4 뒤 왜 \(q=5\)q=5를 반환하나?
다음 p scan은 index 6의 10에서 멈추고 q scan은 index 5의 1에서 멈춥니다. \(p=6\ge q=5\)p=6≥q=5라 교환하지 않고 \(q=5\)q=5를 반환합니다.
\(P(0,5), \text{pivot}=4\)P(0,5), pivot=4에서 두 swap은 무엇인가?
먼저 4와 1을 바꿔 [1,7,2,3,6,4]를 만들고, 다음 scan에서 7과 3을 바꿔 [1,3,2,7,6,4]를 만듭니다. 그 뒤 \(p=3,q=2\)p=3,q=2로 교차합니다.
반환 q 뒤 재귀 범위는 어떻게 쓰나?
Hoare 방식에서는 quicksort(left,q)와 quicksort(q+1,right)입니다. q 자체가 왼쪽 구간에 포함되며 [left,q-1]로 줄이면 원소를 빠뜨릴 수 있습니다.
전체 trace는 어디서 끝나나?
P(0,2), P(1,2), P(3,5), P(3,4), P(6,8), P(7,8)를 거치면 모든 호출 구간이 길이 1이 됩니다. 이 base case들이 모여 전체 정렬을 완성합니다.
답이 맞는지 스스로 검산
- 각 partition 반환 직후 A[left..q]의 모든 값≤pivot이고 A[q+1..right]의 모든 값≥pivot인지 실제 값을 훑습니다.
- 재귀 자식 [left..q], [q+1..right]가 겹치지 않으면서 부모 구간을 빠짐없이 덮고, 둘 다 부모보다 짧은지 확인합니다.
- 최종 배열은 nondecreasing이고 입력의 아홉 값을 같은 개수로 가지므로 정렬 결과 조건을 만족합니다.
30초 자가점검
Hoare partition이 q를 반환하면 pivot은 항상 A[q]인가?
힌트: 첫 P(0,8)의 pivot 10과 반환 \(q=5\)q=5를 비교하세요.
정답: 아닙니다. 첫 partition 뒤 10은 index 6이고 \(q=5\)q=5입니다. 보장은 pivot의 위치가 아니라 두 구간의 ≤/≥ 조건입니다.
[4,1,6]에서 첫 원소 pivot Hoare partition의 반환 q는?
힌트: \(p=-1,q=3\)p=-1,q=3에서 시작해 4와 1을 먼저 찾습니다.
정답: 4↔1 뒤 [1,4,6]이 되고 다음 scan에서 \(p=1,q=0\)p=1,q=0으로 교차하므로 \(q=0\)q=0을 반환합니다.
첫 원소 pivot QuickSort의 worst case가 \(\Theta(n^{2})\)Θ(n²)이 되는 입력은?
힌트: 매번 한 칸과 나머지로 가장 불균형하게 나뉘는 경우를 생각하세요.
정답: 이미 오름차순이거나 내림차순인 배열처럼 첫 pivot이 계속 극값이면 분할이 1 대 n-1에 가까워져 \(\Theta(n^{2})\)Θ(n²)이 됩니다.
실제 문제의 상태 변화를 한 단계씩 재현하기
각 단계에서 무엇을 했는지, 왜 그렇게 했는지, 결과가 무엇인지 차례대로 확인합니다.
수식이 포함된 학습 항목: \(P(0,8), \text{pivot}=10\)
P(0,8), pivot=10\(p=0\)
p=0의 10과 \(q=6\)q=6의 4를 swap합니다. 다음 scan에서 \(p=6,q=5\)p=6,q=5로 교차하여 \(q=5\)q=5를 반환합니다. 재귀 구간은 [0..5], [6..8]입니다.결과 상태 · [4, 7, 2, 3, 6, 1, 10, 13, 29]수식이 포함된 학습 항목: \(P(0,5), \text{pivot}=4\)
P(0,5), pivot=44↔1, 이어서 7↔3을 swap한 뒤 \(p=3,q=2\)
p=3,q=2로 교차하여 \(q=2\)q=2를 반환합니다.결과 상태 · [1, 3, 2, 7, 6, 4, 10, 13, 29]수식이 포함된 학습 항목: \(P(0,2), \text{pivot}=1\)
P(0,2), pivot=1\(p=q=0\)
p=q=0이 되어 \(q=0\)q=0을 반환합니다. 왼쪽은 길이 1이고 오른쪽 [1..2]만 남습니다.결과 상태 · [1, 3, 2, 7, 6, 4, 10, 13, 29]수식이 포함된 학습 항목: \(P(1,2), \text{pivot}=3\)
P(1,2), pivot=33과 2를 swap하고 \(q=1\)
q=1을 반환하여 [1..2]가 정렬됩니다.결과 상태 · [1, 2, 3, 7, 6, 4, 10, 13, 29]수식이 포함된 학습 항목: \(P(3,5), \text{pivot}=7\)
P(3,5), pivot=77과 4를 swap하고 \(q=4\)
q=4를 반환합니다.결과 상태 · [1, 2, 3, 4, 6, 7, 10, 13, 29]수식이 포함된 학습 항목: \(P(3,4), \text{pivot}=4\)
P(3,4), pivot=4swap 없이 \(q=3\)
q=3을 반환합니다. 왼쪽 큰 구간 [0..5] 정렬이 끝납니다.결과 상태 · [1, 2, 3, 4, 6, 7, 10, 13, 29]수식이 포함된 학습 항목: \(P(6,8), \text{pivot}=10\)
P(6,8), pivot=10이미 pivot보다 큰 값들이 오른쪽에 있어 swap 없이 \(q=6\)
q=6을 반환합니다.결과 상태 · [1, 2, 3, 4, 6, 7, 10, 13, 29]수식이 포함된 학습 항목: \(P(7,8), \text{pivot}=13\)
P(7,8), pivot=13swap 없이 \(q=7\)
q=7을 반환하고 모든 재귀 구간이 길이 1이 됩니다.결과 상태 · [1, 2, 3, 4, 6, 7, 10, 13, 29]
마지막에 쓰는 시험 답안 틀
답안 첫 줄에 'pivot=A[left], Hoare partition'을 선언하고 각 partition마다 구간, pivot, swap 후 배열, 반환 q, 다음 재귀 구간을 쓴다. 최종 배열은 [1,2,3,4,6,7,10,13,29]이다.
자주 하는 실수
- partition 방식을 선언하지 않아 trace 기준이 불명확하다.
- Hoare 방식에서 pivot이 항상 q에 있다고 가정한다.
- 재귀 범위를 [left,q-1]과 [q+1,right]로 잘못 쓴다.
- p와 q가 교차한 뒤에도 swap한다.
- partition 한 번으로 양쪽 내부까지 정렬됐다고 생각한다.
- expected \(\Theta(n \log n)\)
Θ(n log n)을 worst-case 보장으로 쓴다.
근거와 정확성 범위
복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
- \(\text{reconstructed}_{\text{exam}}\)
reconstructed(exam)AuD Gedächtnisprotokoll SoSe 2025.md· lines 193-224 · 신뢰도/범위: 복기 문언이며 공식 답안 아님3번 문제의 복기 문언, 배열, 배점, 고유 key 전제, MinSort pseudocode와 15개 빈칸
- \(\text{current}_{\text{lecture}}\)
current(lecture)Vorlesung\02Sorting_updated.pdf· pp. 11, 17-23, 50-55 · 신뢰도/범위: 현재 강의 원문으로 검증Insertion Sort pseudocode, 정확한 prefix invariant와 correctness, best/worst runtime
- \(\text{current}_{\text{lecture}}\)
current(lecture)Vorlesung\02Sorting_updated.pdf· pp. 104-113 · 신뢰도/범위: 현재 강의 원문으로 검증첫 원소 pivot Hoare partition pseudocode와 pointer trace 예시
- \(\text{current}_{\text{lecture}}\)
current(lecture)Vorlesung\02Sorting_updated.pdf· pp. 114-124, 125-135 · 신뢰도/범위: 현재 강의 원문으로 검증Hoare partition termination/correctness와 QuickSort best, worst, randomized expected runtime
- \(\text{official}_{\text{solution}}\)
official(solution)Übung\AuD26_Sheet01-Sol.pdf· pp. 8-12 and 14-16 · 신뢰도/범위: 공식 연습문제 풀이Initialization, Maintenance, Termination 증명 구조와 Insertion Sort의 strict comparison/stability
마지막 생성: 2026-08-02 08:51