7. Sorting (2)

Sorting (2)

---

1. Merge Sort (병합 정렬)

:분할 정복(Divide & Conquer)알고리즘

배열을 반으로 계속 나누어 길이가 1인 배열들로 쪼갠 뒤, 두 정렬된 부분을 병합(merge) 하여 정렬된 전체를 만든다.

 

과정 (예: [5,2,4,1,3])

1. 분할:
   [5,2,4,1,3] → [5,2], [4,1,3]
   [5,2] → [5], [2]
   [4,1,3] → [4], [1,3] → [1], [3]
2. 정복(병합):
   [5] + [2] → [2,5]
   [1] + [3] → [1,3]
   [4] + [1,3] → [1,3,4] (병합 시 비교로 정렬 유지)
   [2,5] + [1,3,4] → [1,2,3,4,5]

각 단계에서 항상 두 부분배열의 첫 원소를 비교해 작은 값을 새 배열에 담으므로,

같은 값이 나오면 앞쪽 배열의 값이 먼저 들어가 안정성(stability) 이 유지된다.

 

코드

MergeSort(A, l, r):
  if l >= r: return
  m = (l + r) / 2
  MergeSort(A, l, m)
  MergeSort(A, m+1, r)
  Merge(A, l, m, r)

Merge(A, l, m, r):
  create temp array T
  i = l, j = m+1, k = 0
  while i <= m and j <= r:
    if A[i] <= A[j]: T[k++] = A[i++]
    else: T[k++] = A[j++]
  copy remaining elements from left or right into T
  copy T back to A[l..r]

 

시간·공간 복잡도

최선	O(n log n)
평균	O(n log n)
최악	O(n log n)
공간	O(n) (보조 배열 필요)
안정성	안정 (stable)

장단점

• 장점: 성능 예측 가능, 안정성, 외부정렬(디스크 기반) 적합, 대규모 데이터에서도 예측 가능 성능
• 단점: 추가 메모리 필요(O(n)), 재귀 오버헤드(스택 깊이 O(log n)), 작은 배열에서는 삽입 정렬보다 느림

---

2. Heap Sort (힙 정렬)

완전 이진 트리(Heap)를 배열로 표현하고 힙 속성(max-heap 또는 min-heap) 을 이용해 정렬.

보통 max-heap을 만든 뒤 루트(최대값)를 맨 끝으로 보내고, 힙 크기를 줄이며 다시 heapify 하는 방식으로 오름차순 정렬을 구현

== 가장 큰 값을 계속 꺼내 뒤에 쌓아 가는 방식

 

과정 (예: [5,2,4,1,3], max-heap 사용)

1. Build-Max-Heap: 배열을 재배치하여 max-heap으로 만듦.
   • 결과(힙 배열): 예 [5,3,4,1,2] (구체는 힙화 방식에 따라 다름)
2. 반복:
   • 루트(최댓값)와 마지막 원소를 swap. (최댓값을 정렬 영역 끝에 고정)
   • 힙 크기 감소(마지막 원소를 힙에서 제거한 것처럼 처리).
   • 루트에서부터 heapify-down 하여 다시 max-heap 복원.
3. 이 과정을 모든 원소가 제자리로 갈 때까지 반복. 모든 원소가 정렬 영역으로 이동하면 완료.

 

코드

heapSort(A):
  n = length(A)
  // build max heap
  for i = floor(n/2)-1 down to 0:
    heapify(A, n, i)
  // extract elements
  for i = n-1 down to 1:
    swap(A[0], A[i])
    heapify(A, i, 0) // heap size reduced by 1

 

시간·공간 복잡도

Build Heap	O(n)
추출 단계	O(n log n)
전체	O(n log n)
공간	O(1) (in-place)
안정성	불안정 (unstable)

 

장단점

• 장점: 추가 메모리 거의 없음(in-place), 최악시간 보장 O(n log n)
• 단점: 불안정, 캐시 효율이 좋지 않아 실제 성능이 퀵 정렬보다 떨어질 수 있음, 구현이 병렬화에 덜 유리
•  

---

정리하자면, 

알고리즘	평균	최악	최선	안정성	특징
Bubble	O(n²)	O(n²)	O(1)	안정	교육용, 거의 정렬된 경우 유리
Selection	O(n²)	O(n²)	O(1)	불안정	swap 횟수 적음
Insertion	O(n²)	O(n²)	O(1)	안정	거의 정렬됨에서 매우 빠름
Quick (일반 최적화)	O(n log n)	O(n²)	O(log n) avg	불안정	평균 최강, 캐시 친화적
Merge	O(n log n)	O(n log n)	O(n)	안정	외부 정렬에 적합, 안정성 필요 시 선택
Heap	O(n log n)	O(n log n)	O(1)	불안정	in-place, 메모리 제한 시 유리

 

• 큰 일반적 데이터: 최적화된 Quicksort 가 보통 가장 빠름(캐시, 상수요인 우수). 다만 최악 케이스 대비 안전성이 필요하면 Merge Sort 또는 Introsort(퀵+힙 혼합) 사용.
• 안정성 필요: Merge Sort 사용. (예: 레코드 정렬에서 동일 키의 상대 순서 유지 필요할 때)
• 메모리 제한: Heap Sort가 추가 공간 거의 없음으로 유리.
• 거의 정렬된 데이터: Insertion Sort가 매우 빠름(실무에서는 작은 블록에 삽입 정렬을 적용).
• 외부 정렬(데이터가 디스크에 크고 메모리에 안 들어갈 때): Merge Sort 기반의 외부 병합 정렬을 사용.