[2026] 정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
![[2026] 정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리](/og/s/algorithm-series-06-sorting-basic.webp)
이 글의 핵심
정렬 알고리즘: 버블, 선택, 삽입 정렬 버블 정렬 (Bubble Sort)·선택 정렬 (Selection Sort).
들어가며
”정렬은 알고리즘의 시작”
정렬은 가장 기본적인 알고리즘입니다. 시간복잡도 분석과 최적화를 배우기에 최고의 주제이며, 버블, 선택, 삽입 정렬은 O(n²) 시간 복잡도를 가지지만 구현이 간단하고 작은 데이터에서는 충분히 실용적입니다.
이 글을 읽으면
- 버블, 선택, 삽입 정렬의 동작 원리를 이해합니다
- 각 정렬의 시간 복잡도와 안정성을 비교합니다
- Python과 C++로 직접 구현할 수 있습니다
- 실무에서 언제 어떤 정렬을 사용할지 판단합니다
목차
1. 버블 정렬 (Bubble Sort)
알고리즘 원리
인접한 두 요소를 비교하며 큰 값을 뒤로 보냅니다. 한 바퀴 돌 때마다 가장 큰 값이 “거품처럼” 맨 뒤로 올라갑니다. 시각화: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
[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 구현
다음은 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개씩 증가합니다. 시각화: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
[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 구현
다음은 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)
알고리즘 원리
정렬된 부분에 새 요소를 삽입합니다. 카드 정렬하듯이 왼쪽은 항상 정렬 상태를 유지합니다. 시각화: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
[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 구현
다음은 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 구현
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 스타일)
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 구현
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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²) 시간 소요 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
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 플래그 추가
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)
증상: 인덱스 범위 실수 아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# 잘못된 예
for i in range(n):
for j in range(n - i): # 범위 초과
if arr[j] > arr[j + 1]:
# IndexError해결: 다음은 간단한 python 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
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 내장 정렬
다음은 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번째수
다음 단계
- 고급 정렬: 퀵/병합/힙 정렬
- 정렬 문제: 정렬 문제 풀이
- 이진 탐색: 이진 탐색 완벽 정리 실무에서는 언어 내장 정렬을 사용하되, 원리를 이해하면 커스텀 정렬이나 최적화가 필요할 때 유리합니다.