정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
이 글의 핵심
정렬 알고리즘에 대한 실전 가이드입니다. 버블, 선택, 삽입 정렬 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며
”정렬은 알고리즘의 시작”
정렬은 가장 기본적인 알고리즘입니다. 시간복잡도 분석과 최적화를 배우기에 최고의 주제이며, 버블, 선택, 삽입 정렬은 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)]추천 문제
백준:
프로그래머스:
다음 단계
- 고급 정렬: 퀵/병합/힙 정렬
- 정렬 문제: 정렬 문제 풀이
- 이진 탐색: 이진 탐색 완벽 정리
실무에서는 언어 내장 정렬을 사용하되, 원리를 이해하면 커스텀 정렬이나 최적화가 필요할 때 유리합니다.