버블 정렬과 삽입 정렬
두 가지 제곱 시간 정렬 알고리즘을 구현하고 O(n²)인 이유와 삽입 정렬이 병합 정렬보다 빠른 한 가지 경우를 이해합니다.
버블 정렬과 삽입 정렬은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
O(n²) 정렬을 공부하는 이유
버블 정렬과 삽입 정렬은 최악의 경우 O(n²)이므로 큰 입력에는 실용적이지 않습니다. 하지만 제대로 된 알고리즘 면접에서는 두 정렬을 구현하고 분석할 수 있어야 합니다. 두 정렬은 비교, 교환, 안정 정렬, 최선의 경우 동작처럼 더 고급 알고리즘에도 적용되는 기본 개념을 가르쳐 줍니다. 면접관은 이를 통해 반복문 불변식과 점근 표기법을 처음부터 논리적으로 설명할 수 있는지 확인합니다.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')버블 정렬: 최댓값 올리기
버블 정렬은 배열을 반복해서 훑으며 순서가 잘못된 인접 원소를 교환합니다. 한 번의 전체 순회가 끝날 때마다 정렬되지 않은 원소 중 가장 큰 원소가 '거품처럼 올라가' 끝의 최종 위치에 놓입니다. n-1번 순회하면 전체 배열이 정렬됩니다. 큰 원소가 거품처럼 위로 떠오르는 모습에서 이름이 유래했습니다. 설명하기에는 가장 간단한 정렬 알고리즘이지만 실제로 사용되는 경우는 드뭅니다.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]조기 종료를 사용하는 버블 정렬
최적화된 버블 정렬은 swapped 플래그를 사용합니다. 내부 순회를 한 번 완료했을 때 교환이 한 번도 발생하지 않으면 배열이 이미 정렬된 것이므로 조기에 종료합니다. 따라서 이미 정렬된 입력에서는 최선의 경우 O(n)이 됩니다. 이것이 버블 정렬의 진정한 장점 하나입니다. 이 플래그가 없으면 항상 O(n²)번 비교를 수행합니다. 버블 정렬의 개선 방법을 물었을 때 면접관이 확인하는 부분이 바로 이 조기 종료 최적화입니다.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 pass버블 정렬의 복잡도 분석
버블 정렬의 외부 반복문은 n-1번 실행됩니다. 내부 반복문은 각 순회에서 n-1-i번 실행됩니다. 즉, (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2번 비교합니다. 따라서 평균 및 최악의 경우 O(n²)입니다. 조기 종료 플래그를 사용하면 정렬된 입력에서 최선의 경우가 O(n)으로 줄어듭니다. 공간 복잡도는 O(1)입니다. 변수 교환에 필요한 임시 변수만 사용하기 때문입니다. 버블 정렬은 안정적입니다. 엄격하게 더 큰 원소만 교환하므로 같은 원소의 상대적 순서가 유지됩니다.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5삽입 정렬: 정렬된 손패 만들기
삽입 정렬은 카드 손패를 정렬하는 방식과 비슷합니다. 다음 카드(원소)를 집어 이미 정렬된 왼쪽 카드 사이의 올바른 위치에 삽입합니다. 불변식은 arr[0:i]가 항상 정렬되어 있다는 것입니다. 새 원소를 처리할 때마다 더 큰 원소를 오른쪽으로 이동해 공간을 만듭니다. 이 제자리 안정 정렬의 최악의 경우는 O(n²)이지만, 거의 정렬된 데이터에서는 최선의 경우 O(n)입니다.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]삽입 정렬 단계별 실행
[3, 1, 4, 2]에 삽입 정렬을 추적해 보겠습니다. i=1, 키=1, 3을 오른쪽으로 이동 → [1, 3, 4, 2]. i=2, 키=4, 이동 없음 → 변경되지 않음. i=3, 키=2, 4와 3을 오른쪽으로 이동 → [1, 2, 3, 4]. 각 원소는 올바른 위치를 찾을 때까지 왼쪽에 있는 원소와 비교됩니다. 내부 while 반복문은 대입을 사용해 이동을 수행합니다. 교환은 한 번에 세 번의 대입이 필요하지만, 이동은 한 번의 대입만 필요하므로 교환보다 빠릅니다.
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]거의 정렬된 데이터에서의 삽입 정렬
삽입 정렬의 강력한 장점은 O(n + 역전 수) 복잡도입니다. 역전은 i < j이지만 arr[i] > arr[j]인 쌍 (i,j)입니다. 역전이 몇 개뿐인 거의 정렬된 배열에서는 삽입 정렬이 매우 빠릅니다. 단순하고 캐시 친화적인 접근 패턴 덕분에 실제로는 병합 정렬보다 빠를 때도 있습니다. 파이썬의 팀소트가 작은 부분 배열에 삽입 정렬을 사용하는 이유도 바로 이것입니다.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)정렬의 안정성
정렬 알고리즘은 정렬 후 같은 원소가 원래의 상대적 순서를 유지하면 안정적이라고 합니다. 버블 정렬과 삽입 정렬은 같은 원소를 절대 교환하지 않으므로 모두 안정적입니다. 여러 키를 순차적으로 정렬할 때 안정성이 중요합니다. 먼저 보조 키로 안정적으로 sort를 수행한 다음, 기본 키로 안정적으로 sort하면 동률인 원소 사이에서 보조 키의 순서가 유지됩니다. 병합 정렬도 안정적이지만, 힙 정렬과 빠른 정렬은 일반적으로 안정적이지 않습니다.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stable이진 검색으로 수행하는 삽입 정렬
삽입 정렬의 내부 반복문은 올바른 위치를 찾는 동시에 원소를 이동합니다. 이진 검색을 사용하면 O(log i)번의 비교로 위치를 찾을 수 있지만, 이동에는 여전히 O(i) 시간이 걸리므로 전체 복잡도는 O(n²)으로 유지됩니다. 이 최적화는 비교 함수의 비용이 큰 경우에 유용하게 비교 횟수를 줄이지만, 전체 연산 수를 줄이지는 않습니다. 이러한 '이진 삽입 정렬'은 팀소트에서 작은 청크 크기에 사용됩니다.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]버블 정렬과 삽입 정렬: 각각 언제 사용할까
면접에서는 다음과 같이 자신 있게 비교하십시오. 삽입 정렬이 버블 정렬보다 확실히 낫습니다. 두 정렬 모두 최악의 경우 O(n²), 공간 복잡도 O(1)이지만, 삽입 정렬은 더 적게 기록하고(k개의 역전에 대해 O(n+k), 버블 정렬은 O(n²)), 캐시 친화적이며, 작은 n에 실용적인 선택입니다(팀소트도 이를 사용합니다). 버블 정렬의 유일한 실제 장점은 교육적으로 단순하다는 점입니다. 실제 운영 환경에서는 항상 해당 언어의 내장 sort를 사용하십시오.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]지표로서의 역전 개수 세기
배열의 역전 개수는 i < j이지만 arr[i] > arr[j]인 쌍 (i,j)의 개수와 같습니다. 삽입 정렬이 수행하는 이동 횟수가 역전 개수와 정확히 같다는 점은 유용한 통찰입니다. 역전을 효율적으로 세려면(O(n log n)) 수정된 병합 정렬이 필요합니다. 면접관은 정렬에 관한 논의의 후속 질문으로 '알고리즘이 역전을 얼마나 고려하나요?'라고 묻기도 합니다.
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs inverted빠른 확인
이 단원에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 얼마나 이해했는지 테스트해 보십시오.
단원 요약
이 단원에서는 다음을 배웠습니다. 버블 정렬은 n-1번 순회하며, 각 순회에서 현재 최댓값을 최종 위치까지 이동시키고, 조기 종료 플래그를 사용하면 최악의 경우 O(n²), 최선의 경우 O(n)이 됩니다. 삽입 정렬은 현재 키를 올바른 정렬 위치에 삽입하기 위해 원소를 오른쪽으로 이동하며, O(n + 역전 수) 시간에 실행되므로 거의 정렬된 데이터에 최적입니다. 또한 두 알고리즘 모두 안정적이고 공간 복잡도는 O(1), 최악의 경우 시간 복잡도는 O(n²)이지만, 실제 모든 상황에서는 삽입 정렬을 버블 정렬보다 우선해야 합니다. 다음에는 병합 정렬을 처음부터 구현합니다.
자주 묻는 질문
“버블 정렬과 삽입 정렬” 강의는 무료인가요?
네 — “버블 정렬과 삽입 정렬” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“버블 정렬과 삽입 정렬”에서 뭘 배우나요?
두 가지 제곱 시간 정렬 알고리즘을 구현하고 O(n²)인 이유와 삽입 정렬이 병합 정렬보다 빠른 한 가지 경우를 이해합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“버블 정렬과 삽입 정렬” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.