서론
정렬은 데이터의 열을 특정 순서에 따라 줄을 세우는 과정이다.
정렬은 분할정복,힙 등의 다양한 알고리즘 기법을 배울 수 있는 주제이다.
다양한 정렬 알고리즘
| 평균 시간복잡도 | 최악 시간복잡도 | 공간복잡도 | 안정정렬 | 비고 | |
|---|---|---|---|---|---|
| 삽입정렬 | $O(N^2)$ | $O(N^2)$ | $O(1)$ | O | 간단한 정렬법 |
| 병합정렬 | $O(n \log_2 n)$ | $O(n \log_2 n)$ | $O(N)$ | O | 최악의 경우에도 빠름 |
| 퀵정렬 | $O(n \log_2 n)$ | $O(1)$ | $O(n \log_2 n)$ | O | 최악인 경우는 O($N^2$)이지만 일반적으로 가장 빠름 |
| 힙정렬 | $O(n \log_2 n)$ | $O(n \log_2 n)$ | $O(1)$ | O | 힙을 활용 |
| 버킷정렬 | $O(N+A)$ | $O(N+A)$ | $O(N+A)$ | O | 정렬하고 싶은 값이 작을 때 유용 |
참고자료
문제 해결력을 높이는 알고리즘과 자료구조(오츠키 켄스케)