정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
이 글의 핵심
정렬 알고리즘: 버블, 선택, 삽입 정렬 버블 정렬 (Bubble Sort)·선택 정렬 (Selection Sort).
시리즈 안내
들어가며
”정렬은 알고리즘의 시작”
정렬은 가장 기본적인 알고리즘입니다. 시간복잡도 분석과 최적화를 배우기에 최고의 주제이며, 버블, 선택, 삽입 정렬은 O(n²) 시간 복잡도를 가지지만 구현이 간단하고 작은 데이터에서는 충분히 실용적입니다.
이 글을 읽으면
- 버블, 선택, 삽입 정렬의 동작 원리를 이해합니다
- 각 정렬의 시간 복잡도와 안정성을 비교합니다
- Python과 C++로 직접 구현할 수 있습니다
- 실무에서 언제 어떤 정렬을 사용할지 판단합니다
1. 버블 정렬 (Bubble Sort)
알고리즘 원리
인접한 두 요소를 비교하며 큰 값을 뒤로 보냅니다. 한 바퀴 돌 때마다 가장 큰 값이 “거품처럼” 맨 뒤로 올라갑니다. 시각화:
[5, 2, 4, 1, 3]
↓ 비교 & 교환
[2, 5, 4, 1, 3] (5 > 2 → 교환)
↓
[2, 4, 5, 1, 3] (5 > 4 → 교환)
↓
[2, 4, 1, 5, 3] (5 > 1 → 교환)
↓
[2, 4, 1, 3, 5] ← 5가 제자리
1회전 완료, 다음 회전은 [2, 4, 1, 3]만 정렬Python 구현
def bubble_sort(arr):
"""
버블 정렬
- 인접 요소 비교
- 최적화: 교환 없으면 조기 종료
"""
n = len(arr)
for i in range(n):
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:
break
return arr
# 테스트
arr = [5, 2, 4, 1, 3]
print(bubble_sort(arr)) # [1, 2, 3, 4, 5]
# 이미 정렬된 경우
arr = [1, 2, 3, 4, 5]
print(bubble_sort(arr)) # [1, 2, 3, 4, 5] (1회전만 실행)C++ 구현
#include <vector>
#include <iostream>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; ++i) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
std::vector<int> arr = {5, 2, 4, 1, 3};
bubbleSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 4 5
return 0;
}시간복잡도
- 최선: O(n) — 이미 정렬됨 (최적화 버전)
- 평균: O(n²)
- 최악: O(n²) — 역순 정렬
- 공간: O(1) — in-place
- 안정: O — 같은 값의 순서 유지
2. 선택 정렬 (Selection Sort)
알고리즘 원리
최솟값을 찾아 맨 앞과 교환합니다. 매 회전마다 정렬된 부분이 1개씩 증가합니다. 시각화:
[5, 2, 4, 1, 3]
↓ 최솟값 1 찾음
[1, 2, 4, 5, 3] ← 1 제자리
↓ 최솟값 2 찾음
[1, 2, 4, 5, 3] ← 2 제자리
↓ 최솟값 3 찾음
[1, 2, 3, 5, 4] ← 3 제자리
↓ 최솟값 4 찾음
[1, 2, 3, 4, 5] ← 완료Python 구현
def selection_sort(arr):
"""
선택 정렬
- 최솟값 선택
- 항상 O(n²)
"""
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 테스트
arr = [5, 2, 4, 1, 3]
print(selection_sort(arr)) # [1, 2, 3, 4, 5]C++ 구현
#include <vector>
#include <algorithm>
#include <iostream>
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; ++i) {
int min_idx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
std::swap(arr[i], arr[min_idx]);
}
}
int main() {
std::vector<int> arr = {5, 2, 4, 1, 3};
selectionSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 4 5
return 0;
}시간복잡도
- 최선: O(n²) — 이미 정렬되어도 최솟값 탐색 필요
- 평균: O(n²)
- 최악: O(n²)
- 공간: O(1)
- 안정: X — 교환 시 순서 바뀔 수 있음
3. 삽입 정렬 (Insertion Sort)
알고리즘 원리
정렬된 부분에 새 요소를 삽입합니다. 카드 정렬하듯이 왼쪽은 항상 정렬 상태를 유지합니다. 시각화:
[5, 2, 4, 1, 3]
[5] 2 4 1 3 ← 5는 정렬됨
[2, 5] 4 1 3 ← 2를 5 앞에 삽입
[2, 4, 5] 1 3 ← 4를 2와 5 사이에 삽입
[1, 2, 4, 5] 3 ← 1을 맨 앞에 삽입
[1, 2, 3, 4, 5] ← 3을 2와 4 사이에 삽입Python 구현
def insertion_sort(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]
j -= 1
arr[j + 1] = key
return arr
# 테스트
arr = [5, 2, 4, 1, 3]
print(insertion_sort(arr)) # [1, 2, 3, 4, 5]
# 거의 정렬된 경우
arr = [1, 2, 4, 3, 5]
print(insertion_sort(arr)) # [1, 2, 3, 4, 5] (빠름)C++ 구현
#include <vector>
#include <iostream>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> arr = {5, 2, 4, 1, 3};
insertionSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 4 5
return 0;
}시간복잡도
- 최선: O(n) — 이미 정렬됨
- 평균: O(n²)
- 최악: O(n²) — 역순 정렬
- 공간: O(1)
- 안정: O — 같은 값은 순서 유지
4. 정렬 비교
기본 정렬 비교표
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 | 특징 |
|---|---|---|---|---|---|---|
| 버블 | O(n) | O(n²) | O(n²) | O(1) | O | 구현 간단, 최적화 가능 |
| 선택 | O(n²) | O(n²) | O(n²) | O(1) | X | 항상 O(n²) |
| 삽입 | O(n) | O(n²) | O(n²) | O(1) | O | 거의 정렬된 배열에 유리 |
고급 정렬 비교
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 |
|---|---|---|---|---|---|
| 퀵 | O(n log n) | O(n log n) | O(n²) | O(log n) | X |
| 병합 | O(n log n) | O(n log n) | O(n log n) | O(n) | O |
| 힙 | O(n log n) | O(n log n) | O(n log n) | O(1) | X |
선택 가이드
| 상황 | 추천 정렬 | 이유 |
|---|---|---|
| n < 10 | 삽입 정렬 | 오버헤드 적음 |
| 거의 정렬됨 | 삽입 정렬 | O(n)에 가까움 |
| 안정 정렬 필요 | 버블/삽입/병합 | 순서 유지 |
| 메모리 제약 | 선택/힙 | In-place |
| 일반 케이스 | 퀵/병합 | O(n log n) |
| 실무 | sort()/sorted() | 최적화됨 |
5. 실무 사례
사례 1: 거의 정렬된 배열 - 삽입 정렬
시나리오: 실시간 센서 데이터가 대부분 정렬되어 들어옴
Python 구현
import time
def benchmark_sorting(arr):
"""
거의 정렬된 배열에서 삽입 정렬 vs 퀵 정렬
"""
arr_insertion = arr.copy()
arr_quick = arr.copy()
# 삽입 정렬
start = time.perf_counter()
insertion_sort(arr_insertion)
insertion_time = time.perf_counter() - start
# 퀵 정렬
start = time.perf_counter()
arr_quick.sort()
quick_time = time.perf_counter() - start
return insertion_time, quick_time
# 거의 정렬된 배열
arr = list(range(1000))
arr[100], arr[101] = arr[101], arr[100] # 2개만 교환
insertion_time, quick_time = benchmark_sorting(arr)
print(f"삽입 정렬: {insertion_time*1000:.2f}ms")
print(f"퀵 정렬: {quick_time*1000:.2f}ms")
# 삽입 정렬: 0.15ms (빠름)
# 퀵 정렬: 0.08ms결론: 거의 정렬된 작은 배열에서는 삽입 정렬이 유리
사례 2: 작은 배열 - 삽입 정렬
시나리오: Timsort와 Introsort는 작은 구간에서 삽입 정렬 사용
Python 구현 (Timsort 스타일)
def timsort_style(arr, threshold=10):
"""
작은 구간은 삽입 정렬
큰 구간은 병합 정렬
"""
if len(arr) < threshold:
return insertion_sort(arr)
mid = len(arr) // 2
left = timsort_style(arr[:mid], threshold)
right = timsort_style(arr[mid:], threshold)
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 테스트
arr = [5, 2, 8, 1, 9, 3, 7, 4, 6]
print(timsort_style(arr))사례 3: 안정 정렬 - 다중 키 정렬
시나리오: 점수로 정렬하되, 같은 점수는 이름 순서 유지
Python 구현
from dataclasses import dataclass
@dataclass
class Student:
name: str
score: int
students = [
Student("Alice", 90),
Student("Bob", 85),
Student("Charlie", 90),
Student("David", 85),
]
# 안정 정렬 (삽입 정렬)
def insertion_sort_students(students):
for i in range(1, len(students)):
key = students[i]
j = i - 1
while j >= 0 and students[j].score < key.score:
students[j + 1] = students[j]
j -= 1
students[j + 1] = key
return students
sorted_students = insertion_sort_students(students.copy())
for s in sorted_students:
print(f"{s.name}: {s.score}")
# 출력 (같은 점수는 원래 순서 유지):
# Alice: 90
# Charlie: 90
# Bob: 85
# David: 856. 트러블슈팅
문제 1: 버블 정렬 최적화 누락
증상: 이미 정렬된 배열도 O(n²) 시간 소요
def bubble_sort_slow(arr):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 이미 정렬된 배열도 n² 비교해결: swapped 플래그 추가
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
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:
break
return arr문제 2: 선택 정렬 안정성
증상: 같은 값의 순서가 바뀜
arr = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd')]
# 선택 정렬 후: [(1, 'b'), (2, 'd'), (3, 'c'), (3, 'a')]
# (3, 'a')와 (3, 'c')의 순서가 바뀜해결: 안정 정렬 사용 (삽입/병합)
arr.sort(key=lambda x: x[0])
# [(1, 'b'), (2, 'd'), (3, 'a'), (3, 'c')] # 순서 유지문제 3: 삽입 정렬 역순 최악
증상: 역순 배열에서 O(n²) 비교 + 이동
arr = list(range(1000, 0, -1))
# 삽입 정렬: 매우 느림해결: 역순이 예상되면 퀵/병합 정렬
arr.sort() # Timsort (O(n log n))문제 4: 오프바이원 (Off-by-One)
증상: 인덱스 범위 실수
# 잘못된 예
for i in range(n):
for j in range(n - i): # 범위 초과
if arr[j] > arr[j + 1]:
# IndexError해결:
for i in range(n):
for j in range(n - 1 - i): # 올바른 범위
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]마무리
기본 정렬 알고리즘은 O(n²) 시간 복잡도를 가지지만, 알고리즘 학습의 출발점입니다.
핵심 요약
- 버블 정렬
- 인접 요소 비교
- 최적화 시 O(n) 가능
- 안정 정렬
- 선택 정렬
- 최솟값 선택
- 항상 O(n²)
- 불안정 정렬
- 삽입 정렬
- 정렬된 부분에 삽입
- 거의 정렬된 배열에 O(n)
- 안정 정렬
실무 적용
| 상황 | 추천 |
|---|---|
| 일반 정렬 | sorted() / list.sort() |
| 작은 배열 (n < 10) | 삽입 정렬 |
| 거의 정렬됨 | 삽입 정렬 |
| 안정 정렬 필요 | 삽입/병합 |
Python 내장 정렬
# sorted(): 새 리스트 반환
arr = [5, 2, 4, 1, 3]
sorted_arr = sorted(arr)
print(arr) # [5, 2, 4, 1, 3] (원본 유지)
print(sorted_arr) # [1, 2, 3, 4, 5]
# sort(): in-place 정렬
arr = [5, 2, 4, 1, 3]
arr.sort()
print(arr) # [1, 2, 3, 4, 5] (원본 변경)
# 역순
arr.sort(reverse=True)
print(arr) # [5, 4, 3, 2, 1]
# 커스텀 키
students = [('Alice', 85), ('Bob', 90), ('Charlie', 80)]
students.sort(key=lambda x: x[1], reverse=True)
print(students)
# [('Bob', 90), ('Alice', 85), ('Charlie', 80)]추천 문제
백준:
- 2750번: 수 정렬하기
- 2751번: 수 정렬하기 2 프로그래머스:
- K번째수
다음 단계
- 고급 정렬: 퀵/병합/힙 정렬
- 정렬 문제: 정렬 문제 풀이
- 이진 탐색: 이진 탐색 완벽 정리 실무에서는 언어 내장 정렬을 사용하되, 원리를 이해하면 커스텀 정렬이나 최적화가 필요할 때 유리합니다.
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 정렬 알고리즘: 버블, 선택, 삽입 정렬 완벽 정리. 버블 정렬 (Bubble Sort)·선택 정렬 (Selection Sort)로 흐름을 잡고 원리·코드·실무 적용을 한글로 정리합니다. Start now. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- 고급 정렬 | 퀵, 병합, 힙 정렬 O(n log n) 완벽 정리
- C++ 정렬 알고리즘 완벽 가이드 | sort·stable_sort·직접 구현 [#54-7]
- C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, 정렬, Sorting, 버블정렬, 선택정렬, 삽입정렬, 코딩테스트 등으로 검색하시면 이 글이 도움이 됩니다.