728x90
반응형
SMALL
정렬 알고리즘 시간복잡도 비교
| 정렬 알고리즘 | 평균 시간복잡도 | 최악 시간복잡도 | 공간복잡도 | 안정성 |
| 선택 정렬 (Selection Sort) | O(n²) | O(n²) | O(1) | ❌ |
| 삽입 정렬 (Insertion Sort) | O(n²) | O(n²) | O(1) | ✅ |
| 버블 정렬 (Bubble Sort) | O(n²) | O(n²) | O(1) | ✅ |
| 퀵 정렬 (Quick Sort) | O(n log n) | O(n²) | O(log n) | ❌ |
| 병합 정렬 (Merge Sort) | O(n log n) | O(n log n) | O(n) | ✅ |
| 힙 정렬 (Heap Sort) | O(n log n) | O(n log n) | O(1) | ❌ |
선택 정렬 (Selection Sort)
아이디어:
전체 중 가장 작은 값을 찾아서 맨 앞과 교환.
A = [5, 2, 4, 1]
과정
1️⃣ 최소값 1 선택 → [1, 2, 4, 5]
2️⃣ 그다음 최소값 2 → [1, 2, 4, 5]
3️⃣ 4는 이미 제자리 → [1, 2, 4, 5]
➡ 특징
- 교환 횟수 적음 (n−1회)
- 데이터 상태와 관계없이 항상 O(n²)
- 안정하지 않음 (같은 값 순서 깨질 수 있음)
삽입 정렬 (Insertion Sort)
아이디어:
앞에서부터 하나씩 꺼내 자기 위치에 삽입.
A = [5, 2, 4, 1]
과정
1️⃣ 2를 5 앞에 삽입 → [2, 5, 4, 1]
2️⃣ 4를 2,5 사이에 삽입 → [2, 4, 5, 1]
3️⃣ 1을 맨 앞에 삽입 → [1, 2, 4, 5]
➡ 특징
- 거의 정렬된 데이터일 때 매우 빠름 (O(n))
- 안정 정렬
- 구현 간단, 실무에서는 소규모 데이터에 자주 사용
버블 정렬 (Bubble Sort)
아이디어:
인접한 두 원소를 비교하며 큰 값을 뒤로 “버블”처럼 이동.
A = [5, 2, 4, 1]
과정
1️⃣ (5,2) → [2,5,4,1]
(5,4) → [2,4,5,1]
(5,1) → [2,4,1,5]
→ 1회전 후 [2,4,1,5]
2️⃣ 반복해서 [1,2,4,5] 완성
➡ 특징
- 구현은 가장 쉬움
- 비효율적 (O(n²))
- 안정 정렬 (같은 값 순서 유지)
728x90
반응형
LIST