1. 버블 정렬 (Bubble Sort)
핵심: 인접한 두 개를 비교해서 큰 걸 뒤로
과정:
[5, 3, 8, 4, 2]
1회전:
5, 3 비교 → 교환 → [3, 5, 8, 4, 2]
5, 8 비교 → 유지 → [3, 5, 8, 4, 2]
8, 4 비교 → 교환 → [3, 5, 4, 8, 2]
8, 2 비교 → 교환 → [3, 5, 4, 2, 8] ← 8이 맨 뒤로!
2회전:
3, 5 비교 → 유지 → [3, 5, 4, 2, 8]
5, 4 비교 → 교환 → [3, 4, 5, 2, 8]
5, 2 비교 → 교환 → [3, 4, 2, 5, 8] ← 5가 제자리!
3회전:
3, 4 비교 → 유지 → [3, 4, 2, 5, 8]
4, 2 비교 → 교환 → [3, 2, 4, 5, 8] ← 4가 제자리!
4회전:
3, 2 비교 → 교환 → [2, 3, 4, 5, 8] ← 완료!
특징:
- 매 회전마다 가장 큰 값이 뒤로 감 (거품이 위로 올라가듯)
- 쉬움
- 느림
시간복잡도:
- 최선: O(n²)
- 평균: O(n²)
- 최악: O(n²)
공간복잡도: O(1)
2. 선택 정렬 (Selection Sort)
핵심: 최소값을 찾아서 맨 앞으로
과정:
[5, 3, 8, 4, 2]
1회전: 전체에서 최소값(2) 찾아서 맨 앞과 교환
[2, 3, 8, 4, 5]
2회전: 나머지에서 최소값(3) 찾음 → 이미 제자리
[2, 3, 8, 4, 5]
3회전: 나머지에서 최소값(4) 찾아서 교환
[2, 3, 4, 8, 5]
4회전: 나머지에서 최소값(5) 찾아서 교환
[2, 3, 4, 5, 8]
완료!특징:
- 매 회전마다 최소값을 선택
- 교환 횟수 적음 (최대 n번)
- 느림
시간복잡도:
- 최선: O(n²)
- 평균: O(n²)
- 최악: O(n²)
공간복잡도: O(1)
3. 삽입 정렬 (Insertion Sort)
핵심: 하나씩 뽑아서 정렬된 부분에 삽입
과정:
[5, 3, 8, 4, 2]
1회전: 3을 정렬된 부분[5]에 삽입
[3, 5, 8, 4, 2]
2회전: 8을 정렬된 부분[3, 5]에 삽입
[3, 5, 8, 4, 2] (이미 제자리)
3회전: 4를 정렬된 부분[3, 5, 8]에 삽입
[3, 4, 5, 8, 2]
4회전: 2를 정렬된 부분[3, 4, 5, 8]에 삽입
[2, 3, 4, 5, 8]
완료!
특징:
- 앞부분은 항상 정렬되어 있음
- 거의 정렬된 배열에서 빠름!
- 카드 정렬하는 것과 비슷
시간복잡도:
- 최선: O(n) ← 이미 정렬됨
- 평균: O(n²)
- 최악: O(n²)
공간복잡도: O(1)
4. 합병 정렬 (Merge Sort)
핵심: 반으로 나누고 합치면서 정렬 (분할 정복)
과정:
[5, 3, 8, 4, 2]
분할:
[5, 3, 8, 4, 2]
↓
[5, 3, 8] | [4, 2]
↓
[5, 3] | [8] | [4, 2]
↓
[5] | [3] | [8] | [4] | [2]
합병:
[3, 5] | [8] | [2, 4]
↓
[3, 5, 8] | [2, 4]
↓
[2, 3, 4, 5, 8]
합병 과정 (자세히):
[3, 5] 와 [2, 4] 합병:
비교: 3 vs 2 → 2가 작음 → [2]
비교: 3 vs 4 → 3이 작음 → [2, 3]
비교: 5 vs 4 → 4가 작음 → [2, 3, 4]
남은 것: 5 → [2, 3, 4, 5]
특징:
- 안정 정렬 (같은 값의 순서 유지)
- 항상 O(n log n)
- 추가 메모리 필요
시간복잡도:
- 최선: O(n log n)
- 평균: O(n log n)
- 최악: O(n log n)
공간복잡도: O(n)
5. 퀵 정렬 (Quick Sort)
핵심: 피벗 기준으로 작은 것 왼쪽, 큰 것 오른쪽
과정:
[5, 3, 8, 4, 2]
피벗: 5 선택
분할:
작은 것: [3, 4, 2] | 피벗: 5 | 큰 것: [8]
[3, 4, 2] 정렬:
피벗: 3 선택
작은 것: [2] | 피벗: 3 | 큰 것: [4]
합치면:
[2, 3, 4, 5, 8]
과정 (자세히):
[5, 3, 8, 4, 2], 피벗=5
i=0, j=4
5 vs 2 → 교환 → [2, 3, 8, 4, 5]
i=1, j=3
3 vs 4 → 유지
최종: [2, 3, 4] | 5 | [8]
특징:
- 평균적으로 가장 빠름!
- 불안정 정렬
- 피벗 선택이 중요
시간복잡도:
- 최선: O(n log n)
- 평균: O(n log n)
- 최악: O(n²) ← 이미 정렬된 경우
공간복잡도: O(log n) (재귀 스택)
정렬 비교표
| 정렬 | 최선 | 평균 | 최악 | 공간 | 안정성 |
| 버블 | O(n²) | O(n²) | O(n²) | O(1) | 안정 |
| 선택 | O(n²) | O(n²) | O(n²) | O(1) | 불안정 |
| 삽입 | O(n) | O(n²) | O(n²) | O(1) | 안정 |
| 합병 | O(n log n) | O(n log n) | O(n log n) | O(n) | 안정 |
| 퀵 | O(n log n) | O(n log n) | O(n²) | O(log n) | 불안정 |
언제 뭘 쓰나?
버블, 선택 :
- 데이터 적을 때 (n < 50)
- 구현 간단
- 실무에서 거의 안 씀
삽입:
- 거의 정렬된 데이터
- 온라인 알고리즘 (데이터 하나씩 들어올 때)
합병:
- 안정 정렬 필요
- 최악 케이스 피해야 할 때
- 외부 정렬 (디스크)
퀵:
- 평균적으로 가장 빠름
- 실무에서 가장 많이 씀
- Python, Java 기본 정렬