§ 1 · 끼워 넣기삽입 정렬의 절차
버블 정렬과 선택 정렬은 둘 다 O(N²)이지만 선택 정렬이 두 배 빠르다. 이제 세 번째 정렬—삽입 정렬(insertion sort)—을 배운다. 이 알고리즘은 최악의 경우를 넘어선 시나리오 분석의 힘을 보여준다.
① 제거 — 인덱스 1부터, 현재 값을 임시 변수(temp_value)에 빼낸다. 빈 간격이 생긴다.
② 이동 — 간격 왼쪽 값들을 temp와 비교한다. temp보다 크면 오른쪽으로 민다(간격이 왼쪽으로 이동).
③ 삽입 — temp보다 작은 값을 만나거나 왼쪽 끝에 닿으면, temp를 현재 간격에 넣는다.
④ 반복 — 배열이 완전히 정렬될 때까지 ①~③을 반복한다.
§ 2 · 한 단계씩삽입 정렬 실행
배열 [4, 2, 7, 1, 3]을 삽입 정렬한다. 값 하나를 빼내 임시 보관하고, 왼쪽의 큰 값들을 밀어낸 다음 알맞은 간격에 끼워 넣는다.
def insertion_sort(array): for index in range(1, len(array)): position = index temp_value = array[index] while position > 0 and array[position - 1] > temp_value: array[position] = array[position - 1] position = position - 1 array[position] = temp_value
§ 3 · 네 종류 단계삽입 정렬의 효율성
삽입 정렬에는 네 종류의 단계가 있다 — 제거·비교·이동·삽입. 최악의 경우(역순 정렬)에는 각 패스스루에서 temp 왼쪽의 모든 값을 비교하고 이동해야 한다.
§ 4 · 종 곡선평균적인 경우
정의상 가장 자주 발생하는 것은 평균의 경우다. 최악과 최선은 종 곡선의 양 끝, 드물게만 일어난다. 무작위로 정렬된 배열이 완벽한 오름차순일 확률이 얼마나 되겠는가?
삽입 정렬은 시나리오에 따라 극적으로 다르다.
- 최악(역순) — 모든 값을 비교·이동.
N²단계. - 최선(이미 정렬됨) — 패스당 비교 1번, 이동 0번.
약 N단계. - 평균(무작위) — 데이터의 약 절반을 비교·이동.
약 N²/2단계.
§ 5 · 한 단어의 힘break 한 단어
두 배열의 교집합(intersection)을 구하는 함수를 보자. 중첩 루프로 두 배열의 모든 값을 비교한다 — O(N²)다. 그런데 공통 값을 찾는 순간, 내부 루프를 계속 돌 이유가 없다. 이미 일치를 확인했으니까.
function intersection(first_array, second_array){ var result = []; for (var i = 0; i < first_array.length; i++) { for (var j = 0; j < second_array.length; j++) { if (first_array[i] == second_array[j]) { result.push(first_array[i]); break; // 일치 발견 — 내부 루프 탈출 } } } return result; }
break 한 단어로, 두 배열이 같은 최선의 경우는 N²이 아니라 N번 비교로 줄어든다. 빅 오 등급은 그대로 O(N²)지만, 평균의 경우 성능은 N과 N² 사이로 끌어내려진다. 이것이 낙관적 시나리오 최적화다.
§ 6 · 정리이 장이 남긴 것
최선·평균·최악의 시나리오를 구별하는 능력은 가장 적합한 알고리즘을 고르고, 기존 알고리즘을 더 빠르게 만드는 핵심 기술이다. 최악에 대비하되, 평균이 대부분의 시간을 차지한다는 사실을 기억하라.