# Sorting

• 2026년 6월 27일 알고리즘
  quick sort — 최악 O(n²)인데 평균은 왜 O(n log n)인가

  quick sort는 pivot으로 배열을 가르는 분할 정복이다. 두 포인터 분할 과정을 보고 최선 O(n log n)과 최악 O(n²)이 갈리는 지점을 짚는다. 핵심은 평균 분석이다. 기댓값 점화식 E(n)을 세워 평균이 Θ(n log n)임을 유도한다.

• 2026년 6월 25일 알고리즘
  분할 정복 — 나누어 풀고, 정렬의 한계를 증명하다

  분할 정복은 문제를 나눠 풀고 합치는 전략이다. merge sort의 점화식을 대입법으로 풀어 O(n log n)을 유도하고, 메모리 약점과 대안 heap sort를 본다. 비교 기반 정렬이 Ω(n log n)보다 빠를 수 없음을 결정 트리로 증명한다.

• 2026년 5월 18일 알고리즘
  정렬 알고리즘 — Selection / Merge / Quick

  selection·merge·quick sort의 동작 원리를 코드 수준에서 보고, 각 정렬의 올바름을 루프 불변식과 귀납법으로 증명한다. 시간 복잡도 O(n²)·O(n log n)·평균 O(n log n)의 차이가 어디서 오는지 정리한다.