- Published on
[ Algorithm ] 정렬 알고리즘 비교
- Authors
- Name
- 유사공대생
정렬 알고리즘의 비교
| 정렬 알고리즘 | 평균 | 최악 | 메모리 | 안정성 |
|---|---|---|---|---|
| 버블 정렬 | O(N2) | O(N2) | O(1) | O |
| 선택 정렬 | O(N2) | O(N2) | O(1) | X |
| 삽입 정렬 | O(N2) | O(N2) | O(1) | O |
| 퀵 정렬 | O(NlogN) | O(N2) | O(logN) | X |
| 병합 정렬 | O(NlogN) | O(NlogN) | O(N) | O |
| 힙 정렬 | O(NlogN) | O(NlogN) | O(1) | X |
상황에 따른 정렬 알고리즘 선택
기본 - 퀵정렬
- C도 qsort() 함수를 기본 제공
간단히 구현할 때 - 버블 정렬
- 구현이 매우 쉬움
- 10년 안써도 까먹을 수 없음
어떠한 경우에도 느려지면 안 될 때 - 병합 또는 힙 정렬
- 평균은 퀵 정렬보다 느림
- 최악의 경우 여전히 O(NlogN)
특수한 상황에 적합한 정렬 알고리즘
- 예: 기수(radix) 정렬