알고리즘 학습 · 정렬
같은 배열을 8가지 방법으로 정렬해 봐요
모두 [6, 2, 8, 4, 9, 1, 5]에서 시작해요. 하나를 고르면 한 단계씩 넘기며 봐요.
O(n²) · 단순하지만 느려요
O(n log n) · 나눠서 빨라요
비교하지 않아요
한눈에 비교해요
| 방법 | 평균 | 최악 | 추가 공간 | 같은 값 순서 유지 |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | 예 |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | 예 |
| 선택 정렬 | O(n²) | O(n²) | O(1) | 아니요 |
| 쉘 정렬 | O(n log² n) | O(n²) | O(1) | 아니요 |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | 아니요 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | 예 |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | 아니요 |
| 계수 정렬 | O(n + k) | O(n + k) | O(k) | 예 |
버블 정렬평균 O(n²) · 최악 O(n²) · 추가 공간 O(1) · 순서 유지 예삽입 정렬평균 O(n²) · 최악 O(n²) · 추가 공간 O(1) · 순서 유지 예선택 정렬평균 O(n²) · 최악 O(n²) · 추가 공간 O(1) · 순서 유지 아니요쉘 정렬평균 O(n log² n) · 최악 O(n²) · 추가 공간 O(1) · 순서 유지 아니요퀵 정렬평균 O(n log n) · 최악 O(n²) · 추가 공간 O(log n) · 순서 유지 아니요병합 정렬평균 O(n log n) · 최악 O(n log n) · 추가 공간 O(n) · 순서 유지 예힙 정렬평균 O(n log n) · 최악 O(n log n) · 추가 공간 O(1) · 순서 유지 아니요계수 정렬평균 O(n + k) · 최악 O(n + k) · 추가 공간 O(k) · 순서 유지 예