728x90
반응형
다양한 정렬 알고리즘 🔗
거품 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬
📌 거품 정렬 (Bubble Sort)
- 인접한 두 원소를 비교하여 잘못된 순서라면 교환 → 큰 값이 점점 뒤로 "거품처럼" 밀려남
- 시간 복잡도:
- 최악/평균: O(n²)
- 최선(이미 정렬된 경우): O(n)
- 과정:
[5, 3, 8, 4] → (5,3) 비교 → [3,5,8,4]
[3,5,8,4] → (5,8) 비교 → 그대로
[3,5,8,4] → (8,4) 교환 → [3,5,4,8]
📌 삽입 정렬 (Insertion Sort)
- 현재 원소를 그 앞의 정렬된 부분에 "삽입"
- 시간 복잡도:
- 최악/평균: O(n²)
- 최선(이미 정렬): O(n)
- 과정:
[5, 3, 8, 4]
→ 5 | 3,8,4
→ 3,5 | 8,4
→ 3,5,8 | 4
→ 3,4,5,8
📌 선택 정렬 (Selection Sort)
- 남은 구간에서 "가장 작은 값"을 선택하여 앞으로 보냄
- 시간 복잡도:
- 최악/평균/최선: O(n²) (항상 비교해야 함)
- 과정:
[5, 3, 8, 4]
→ 가장 작은 3 ↔ 5 → [3,5,8,4]
→ 나머지 [5,8,4] → 가장 작은 4 ↔ 5 → [3,4,8,5]
→ 나머지 [8,5] → 가장 작은 5 ↔ 8 → [3,4,5,8]
📌 퀵 정렬 (Quick Sort)
- 기준 값(pivot)을 정해, 작은 값은 왼쪽, 큰 값은 오른쪽 → 재귀적으로 반복
- 시간 복잡도:
- 평균: O(n log n)
- 최악(정렬된 배열에서 pivot이 계속 끝에 잡히는 경우): O(n²)
- 과정:
[5, 3, 8, 4], pivot=5
→ [3,4] | 5 | [8]
→ [3,4] 정렬 → [3,4]
최종: [3,4,5,8]
📌 병합 정렬 (Merge Sort)
- 배열을 반으로 계속 나눠서 정렬한 뒤 합침
- 시간 복잡도:
- 최악/평균/최선: O(n log n)
- 과정:
[5, 3, 8, 4]
→ [5,3] [8,4]
→ [5] [3] [8] [4]
→ [3,5] [4,8]
→ [3,4,5,8]
📊 정렬 알고리즘 비교
| 알고리즘 | 특징 | 최선 | 평균 | 최악 |
| 버블 정렬 | 구현 쉽지만 느림 | O(n) | O(n²) | O(n²) |
| 삽입 정렬 | 거의 정렬된 경우 빠름 | O(n) | O(n²) | O(n²) |
| 선택 정렬 | 교환 횟수 최소화 | O(n²) | O(n²) | O(n²) |
| 퀵 정렬 | 평균적으로 가장 빠름 | O(n log n) | O(n log n) | O(n²) |
| 병합 정렬 | 안정적, 병렬 처리에 유리 | O(n log n) | O(n log n) | O(n log n) |
✅ 정리
- O(n²) 계열 (버블, 삽입, 선택) → 구현 쉬움, 작은 데이터에서만 사용
- O(n log n) 계열 (퀵, 병합) → 큰 데이터에서 성능 우수
728x90
반응형