정렬 전략과 작업량
한 권씩 옆과 비교해 옮기는 방식(버블)과 반씩 나눠 정렬한 뒤 합치는 방식(병합)은 작업량이 다르다. 비교·이동 카운터가 그 차이를 수치로 보여준다.
동일 배열에 대한 정렬 알고리즘별 비교·교환 횟수 측정과 시각화.
같은 배열을 버블, 병합, 퀵 정렬로 각각 돌려 비교와 교환 횟수를 실시간으로 세고, n^2와 n log n의 차이가 어디서 벌어지는지 막대 애니메이션으로 확인합니다.
버블 정렬은 이웃한 두 값을 끝없이 비교하며 큰 값을 뒤로 밀어낸다 — 단순하지만 비교 횟수가 n²으로 폭발한다. 병합 정렬은 배열을 반으로 쪼개 정렬된 두 조각을 합치는 일을 재귀적으로 반복해 어떤 입력에서도 n log n을 보장한다. 퀵 정렬은 피벗을 기준으로 작은 값과 큰 값을 가르는 분할을 반복하며, 평균적으로 가장 빠르지만 피벗 운이 나쁘면 n²로 무너진다.
시간복잡도 O(n^2) vs O(n log n)
merge sort: T(n) = 2 * T(n/2) + O(n)
한 권씩 옆과 비교해 옮기는 방식(버블)과 반씩 나눠 정렬한 뒤 합치는 방식(병합)은 작업량이 다르다. 비교·이동 카운터가 그 차이를 수치로 보여준다.
파이썬과 자바의 기본 정렬인 Timsort는 실제 데이터가 대체로 거의 정렬되어 있다는 관찰에서 출발했다. nearly sorted 입력에서 병합 정렬의 이동 횟수가 크게 줄어든다. 입력 분포가 알고리즘 선택을 결정한다.
n개의 순열은 n!가지이고 비교 1회는 경우의 수를 절반으로만 줄인다. 따라서 어떤 비교 정렬도 log₂(n!) ≈ n log n 미만으로 내려갈 수 없다. 역순 입력의 버블 정렬은 반대편 극단인 O(n²)을 보여준다.