[Data Structure] 정렬 시간복잡도
2021. 12. 31. 14:33ㆍMajor`/자료구조
정렬 별 시간복잡도
| 정렬 | 시간복잡도 | 공간복잡도 | 정렬상태 | ||
| 최선 | 평균 | 최악 | |||
| 계수 정렬 Counting Sort |
O(n+k) | O(n+k) | O(n+k) | O(k) | Stable |
| 기수 정렬 Radix Sort |
O(nk) | O(nk) | O(nk) | O(n+k) | Stable |
| 팀 정렬 Tim Sort |
O(n) | O(n log n) | O(n log n) | O(n) | |
| 히프 정렬 Heap Sort |
O(n log n) | O(n log n) | O(n log n) | O(1) | Unstable |
| 합병 정렬 Merge Sort |
O(n log n) | O(n log n) | O(n log n) | O(n) | Stable |
| 쉘 정렬 Shell Sort |
O(n) | O(n1.5) | O(n1.5) | O(1) | Unstable |
| 퀵 정렬 Quick Sort |
O(n log n) | O(n log n) | O(n²) | O(log n) | Unstable |
| 트리 정렬 Tree Sort |
O(n log n) | O(n log n) | O(n²) | O(n) | |
| 삽입 정렬 Insertion Sort |
O(n) | O(n²) | O(n²) | O(1) | Stable |
| 버블 정렬 Bubble Sort |
O(n²) | O(n²) | O(n²) | O(1) | Stable |
| 선택 정렬 Selection Sort |
O(n²) | O(n²) | O(n²) | O(1) | Unstable |
안정 정렬 (Stable Sort)
정렬되지 않은 상태에서, 같은 키를 가진 원소의 순서가 정렬 후에도 유지되는 정렬
- Counting / Radix / Merge / Insertion / Bubble
※ Example
- 3 5(a) 1 4 5(b) 2
- 정렬 후 → 1 2 3 4 5(a) 5(b)
- 같은 키값의 원소의 순서가 유지
불안정 정렬 (Unstable Sort)
정렬되지 않은 상태에서, 같은 키를 가진 원소의 순서가 정렬 후에 유지되는 것을 보장할 수 없는 정렬
- Heap / Shell / Quick / Selection
※ Example
- 3 5(a) 1 4 5(b) 2
- 정렬 후 → 1 2 3 4 5(b) 5(a)
- 같은 키값의 원소의 순서가 유지되지 않는다
