3. Sortieralgorithmen (10 Punkte)

3.1(a) · 삽입 정렬(Insertion Sort) — 정렬된 왼쪽 구간을 한 칸씩 키우기

선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

시험 문언과 배열, 배점, 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²)

먼저 문제의 정체를 줄글로 이해하기

Insertion Sort는 카드 정리와 같습니다. 왼쪽에는 이미 정렬된 카드 묶음이 있고, 오른쪽에서 카드 한 장 key를 꺼내 왼쪽의 알맞은 위치까지 밀어 넣습니다.

반복 j가 시작될 때 A[0..j-1]은 이미 정렬되어 있다는 약속이 핵심입니다. \(\text{key}=A[j]\)key=A[j]보다 큰 원소들을 오른쪽으로 한 칸씩 이동한 뒤 빈자리에 key를 넣으면 정렬 구간이 A[0..j]로 한 칸 커집니다.

이 문항은 최종 배열만 쓰면 부족합니다. 어느 key를 골랐고 어떤 원소가 이동했는지, 매 단계 뒤 정렬된 prefix가 어디까지인지 보여 주어야 합니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 인덱스(index)와 앞구간(prefix)

배열 index는 0부터 8까지입니다. \(j=1\)j=1부터 시작하는 이유는 A[0] 하나만 있는 prefix는 이미 정렬되어 있기 때문입니다.

prefix A[0..j-1]은 배열의 맨 왼쪽에서 j개 원소를 뜻합니다. 이 영역은 원래 입력 prefix와 같은 원소를 가지며 정렬되어 있다고 믿고 다음 key를 삽입합니다.

수식으로 정확히 쓰기

핵심 규칙I(j):\quad A[0{:}j-1]=\operatorname{sort}\!\left(\(A_{0}\)A₀[0{:}j-1]\right)

\[\mathrm{key}=A[j]\]\mathrm{key}=A[j]
개념 2

1단계 · 한 칸 밀기(shift)와 맞바꾸기(swap)

표준 Insertion Sort는 key를 임시 저장하고 key보다 큰 prefix 원소를 오른쪽으로 shift합니다. 마지막에 key를 빈 위치에 한 번 기록합니다.

인접 swap을 반복하는 구현도 같은 중간 순서를 만들 수 있지만, 답안에서는 강의 pseudocode에 맞춰 key·shift·insert를 표시하는 편이 명확합니다.

수식으로 정확히 쓰기

핵심 규칙\text{while } i\ge 0 \land A[i]>\mathrm{key}:\quad A[i+1]\gets A[i]

\[A[i+1]\gets\mathrm{key}\]A[i+1]\gets\mathrm{key}
개념 3

2단계 · 왜 올바른가

시작할 때 정렬된 prefix에서 key보다 큰 것만 오른쪽으로 이동합니다. key 이하의 마지막 원소 바로 뒤에 key가 들어가므로 새 prefix도 정렬됩니다.

값을 새로 만들거나 버리지 않고 이동만 하므로 원래 배열과 같은 multiset을 유지합니다. 정렬성과 원소 보존 두 조건이 함께 correctness를 만듭니다.

수식으로 정확히 쓰기

핵심 규칙\text{정렬된 앞구간}+\text{원소 보존}\Longrightarrow\text{올바른 앞구간}

개념 4

3단계 · 시간복잡도

이미 정렬된 배열에서는 각 기준값(key)이 바로 멈춰 최선의 경우 \(\Theta(n)\)Θ(n)입니다. 역순 배열에서는 j번째 기준값이 앞구간(prefix) 전체를 지나 이동 횟수가 \(1+2+...+(n-1)=\Theta(n^{2})\)1+2+...+(n-1)=Θ(n²)입니다.

이 문제는 실행 추적(trace)이 중심이지만, 왜 마지막 13과 29에서 이동이 없는지도 최선의 경우 한 단계의 모습으로 이해할 수 있습니다.

수식으로 정확히 쓰기

\[T_{\text{최선}}(n)=\Theta(n)\]T_{\text{최선}}(n)=\Θ(n)
\[T_{\text{최악}}(n)=\Theta(n^{2})\]T_{\text{최악}}(n)=\Θ(n²)
\[S(n)=\Theta(1)\]S(n)=\Θ(1)
초보자용 연결 강의

이 소문제를 왜 배우나

Insertion Sort는 ‘이미 해결한 왼쪽 부분을 한 칸 확장한다’는 가장 기본적인 알고리즘 사고를 보여 줍니다. 이 한 문제를 제대로 따라가면 배열 index, 비교와 이동, 안정성, loop invariant를 서로 연결해 설명할 수 있습니다.

풀이 전에 꼭 알아야 할 말

배열과 인덱스(index)

배열은 값을 순서대로 담은 칸들의 줄이고 인덱스는 칸 번호입니다. 이 알고리즘은 첫 칸을 0으로 세므로 길이 n의 마지막 인덱스는 n-1입니다.

아주 작은 예: [8,3,5]에서 \(A[0]=8, A[2]=5\)A[0]=8, A[2]=5입니다.

오름차순(sorted)

왼쪽 값이 바로 오른쪽 값보다 크지 않은 상태입니다. 모든 인접 쌍에 대해 \(A[k]\le A[k+1]\)A[k]≤A[k+1]이면 배열 전체가 오름차순입니다.

아주 작은 예: [2,2,7]은 정렬, [2,7,3]은 \(7>3\)7>3이라 미정렬입니다.

앞구간(prefix)과 기준값(key)

앞구간은 맨 왼쪽부터 이어지는 구간입니다. j번째 반복에서는 A[0..j-1]가 이미 정렬된 앞구간이고 A[j]를 기준값으로 꺼냅니다.

아주 작은 예: \(j=3\)j=3일 때 [2,7,10]이 앞구간이고 3이 기준값입니다.

중복을 세는 원소 모음(multiset)

각 값이 몇 번 나오는지까지 세는 원소 모음입니다. 올바른 정렬은 순서만 맞추는 것이 아니라 입력의 모든 값을 같은 개수로 보존해야 합니다.

아주 작은 예: [2,2,5]와 [2,5]는 2의 개수가 달라 같은 원소 모음이 아닙니다.

손에 든 카드를 한 장씩 끼워 넣기

왼손에는 이미 작은 순서로 정리된 카드 묶음이 있고 오른쪽에서 카드 한 장을 뽑습니다. 새 카드보다 큰 카드들을 오른쪽으로 한 칸씩 밀어 빈틈을 만든 뒤, 새 카드를 그 틈에 넣습니다. 그러면 정리된 묶음이 정확히 한 장 커집니다.

이미 정리된 왼손 카드
↔
정렬된 prefix A[0..j-1]
오른쪽에서 뽑은 한 장
↔
임시 저장한 \(\text{key}=A[j]\)key=A[j]
큰 카드를 한 칸 밀기
↔
\(A[i+1]=A[i] \text{shift}\)A[i+1]=A[i] shift
생긴 틈에 카드 넣기
↔
\(A[i+1]=\text{key}\)A[i+1]=key

비유의 한계: 실제 배열에는 물리적인 빈칸이 생기지 않습니다. key를 변수에 임시 저장했기 때문에 덮어써도 값이 사라지지 않는다는 점을 코드로 함께 보아야 합니다.

한 반복의 네 상태

① 정렬된 앞구간(prefix)[2,7,10]은 이미 정렬되어 있다고 가정합니다.
② 기준값 꺼내기(lift key)\(j=3\)j=3의 값 3을 기준값 변수에 안전하게 보관합니다.
③ 오른쪽으로 밀기(shift)10과 7은 3보다 크므로 오른쪽으로 한 칸씩 이동합니다.
④ 기준값 넣기(insert)\(2\le 3\)2≤3에서 멈추고 그 바로 뒤에 3을 기록합니다.

항상 ‘prefix 확인 → key 보관 → 큰 값 \(\text{shift} \to \text{key}\)shift → key삽입’ 순서입니다. 아직 처리하지 않은 suffix는 이번 반복의 정렬 보장 대상이 아닙니다.

먼저 작은 예제로 연습 · [5,2,4]에서 \(j=1\)j=1과 \(j=2\)j=2

맨 처음 \(A[0]=5\)A[0]=5하나는 정렬된 prefix입니다. 매 단계에서 key를 먼저 적고, 비교가 참일 때만 shift합니다.

\(j=1, \text{key}=2\)j=1, key=2보관

\(A[0]=5\)A[0]=5하나는 이미 정렬되어 있고 다음 값 2를 그 안에 넣어야 합니다.

prefix [5] | key 2 | suffix [4]
5를 오른쪽으로 shift

\(5>2\)5>2이므로 while 조건이 참이고 \(A[1]=5\)A[1]=5로 복사한 뒤 \(i=-1\)i=-1이 됩니다.

\([5,5,4], \text{key}=2\)[5,5,4], key=2는 변수에 보존
빈 위치 A[0]에 2 삽입

\(i<0\)i<0이므로 더 비교할 prefix 원소가 없고 \(A[i+1]=A[0]\)A[i+1]=A[0]이 삽입 위치입니다.

[2,5,4]
\(j=2, \text{key}=4\)j=2, key=4처리

\(5>4\)5>4라 5만 밀고 \(2\le 4\)2≤4에서 멈추므로 4는 두 값 사이에 들어갑니다.

[2,4,5]

작은 예제의 결론: 각 반복이 끝날 때 정렬된 prefix가 한 칸 커지고 값은 이동만 하므로, 마지막에는 전체 배열이 입력과 같은 원소를 가진 정렬 배열이 됩니다.

이제 실제 시험 문제에 연결

처음 \(j=1\)j=1에서 무엇을 비교하나?

\(\text{key}=7\)key=7을 저장하고 prefix의 마지막 \(A[0]=10\)A[0]=10과 비교합니다. \(10>7\)10>7이라 10을 A[1]로 밀고 경계를 지나면 7을 A[0]에 넣어 [7,10,...]을 만듭니다.

\(j=3, \text{key}=3\)j=3, key=3은 왜 index 1에 들어가나?

정렬 prefix [2,7,10]을 뒤에서 보며 10과 7을 밀고, 처음으로 3보다 크지 않은 2를 만납니다. 따라서 2의 바로 다음 칸 A[1]이 정확한 삽입 위치입니다.

\(j=5, \text{key}=1\)j=5, key=1에서는 왜 다섯 번 shift하나?

prefix [2,3,6,7,10]의 모든 값이 1보다 크므로 while이 경계 \(i=-1\)i=-1까지 계속됩니다. key는 임시 변수에 있으므로 다섯 칸을 밀어도 1은 사라지지 않습니다.

\(j=6\)j=6뒤 무엇이 보장되나?

새 \(\text{prefix} A[0..6]=[1,2,3,4,6,7,10]\)prefix A[0..6]=[1,2,3,4,6,7,10]이 정렬됩니다. 남은 13과 29도 이미 그보다 크므로 화면상 전체 배열이 정렬되어 이후 답안 그림은 생략할 수 있지만 표준 loop 자체는 계속됩니다.

답이 맞는지 스스로 검산

  • 인접한 모든 쌍을 확인하면 \(1\le 2\le 3\le 4\le 6\le 7\le 10\le 13\le 29\)1≤2≤3≤4≤6≤7≤10≤13≤29이므로 nondecreasing 조건을 만족합니다.
  • 입력과 출력에 1,2,3,4,6,7,10,13,29가 각각 한 번씩 있어 multiset이 보존되었습니다.
  • 각 j 뒤 A[0..j]만 따로 읽어도 정렬되어 있으며, 그 구간은 원래 \(A_{0}[0..j]\)A₀[0..j]의 값들을 정확히 한 번씩 포함합니다.

30초 자가점검

[3,3*,2]에서 두 번째 3*을 처리할 때 먼저 있던 3과 순서가 바뀌나?

힌트: while 조건은 ≥가 아니라 엄격한 >입니다.

정답: 바뀌지 않습니다. \(3>3\cdot \)3>3*이 거짓이라 shift하지 않고 3*은 기존 3의 오른쪽에 남으므로 안정적입니다.

[8,4,6]의 \(j=2, \text{key}=6\)j=2, key=6뒤 배열은 무엇인가?

힌트: 정렬 prefix [4,8]을 뒤에서 한 칸씩 비교합니다.

정답: 8만 오른쪽으로 밀고 \(4\le 6\)4≤6에서 멈춰 [4,6,8]이 됩니다.

정렬된 결과만 확인하면 correctness 검산이 끝나는가?

힌트: 값을 잃거나 복제한 잘못된 알고리즘을 생각해 보세요.

정답: 아닙니다. nondecreasing뿐 아니라 출력 multiset이 입력 multiset과 같은지도 확인해야 올바른 정렬입니다.

실제 문제의 상태 변화를 한 단계씩 재현하기

각 단계에서 무엇을 했는지, 왜 그렇게 했는지, 결과가 무엇인지 차례대로 확인합니다.

  1. 초기

    \(A[0]=10\)A[0]=10하나는 이미 정렬된 prefix입니다.

    결과 상태 · [10, 7, 2, 3, 6, 1, 4, 13, 29]

  2. 수식이 포함된 학습 항목: \(j=1\)j=1

    \(10>7\)10>7이므로 10을 오른쪽으로 밀고 7을 A[0]에 넣습니다.

    결과 상태 · [7, 10, 2, 3, 6, 1, 4, 13, 29]

  3. 수식이 포함된 학습 항목: \(j=2\)j=2

    10과 7을 차례로 밀고 2를 맨 앞에 넣습니다.

    결과 상태 · [2, 7, 10, 3, 6, 1, 4, 13, 29]

  4. 수식이 포함된 학습 항목: \(j=3\)j=3

    10과 7을 밀고 \(2\le 3\)2≤3에서 멈춰 그 뒤에 3을 넣습니다.

    결과 상태 · [2, 3, 7, 10, 6, 1, 4, 13, 29]

  5. 수식이 포함된 학습 항목: \(j=4\)j=4

    10과 7을 밀고 \(3\le 6\)3≤6뒤에 6을 넣습니다.

    결과 상태 · [2, 3, 6, 7, 10, 1, 4, 13, 29]

  6. 수식이 포함된 학습 항목: \(j=5\)j=5

    prefix의 모든 원소가 1보다 커서 다섯 개를 밀고 1을 맨 앞에 넣습니다.

    결과 상태 · [1, 2, 3, 6, 7, 10, 4, 13, 29]

  7. 수식이 포함된 학습 항목: \(j=6\)j=6

    10,7,6을 밀고 \(3\le 4\)3≤4뒤에 4를 넣습니다. 이 시점에 전체 배열이 이미 정렬되었습니다.

    결과 상태 · [1, 2, 3, 4, 6, 7, 10, 13, 29]

  8. 수식이 포함된 학습 항목: \(j=7,8\)j=7,8

    13과 29는 각각 prefix의 마지막 값 이상이므로 이동이 없습니다. 표준 loop는 이 비교를 실행하지만 문제 힌트에 따라 답안의 무변경 그림은 생략해도 됩니다.

    결과 상태 · [1, 2, 3, 4, 6, 7, 10, 13, 29]

마지막에 쓰는 시험 답안 틀

각 줄에 j, key, 이동한 값, 결과 배열을 기록한다. 최종 결과는 [1,2,3,4,6,7,10,13,29]이다.

자주 하는 실수

근거와 정확성 범위

복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.

마지막 생성: 2026-08-02 08:51