기수정렬(Radix Sort)
개념
- 자릿수를 기준으로 정렬하는 알고리즘
- 비교를 하지 않는 알고리즘
- 양수만 가능
과정
특징
- Least Significant Digit(LSD)
- 안정정렬
- 추가적인 메모리 공간 필요
- 정렬 대상의 모든 길이가 동일해야 효율적
시간 복잡도
- O(dN) => N은 데이터의 개수, d는 데이터들의 최대 자리 수
Q. 왜 주로 낮은 자리 수부터 정렬?
A. LSD의 경우 10000와 1을 비교할 때, Digit의 갯수만큼 확인
but MSD의 경우 중간에 정렬이 완료되면 더 살펴볼 필요가 없음
LSD의 코드 구현이 MSD에 비해 간결
'CS STUDY > 알고리즘' 카테고리의 다른 글
| 이분 탐색(Binary Search) (0) | 2024.03.19 |
|---|---|
| 계수정렬(Counting Sort) (0) | 2024.03.19 |
| 힙 정렬(Heap Sort) (0) | 2024.03.12 |
| 병합 정렬(Merge Sort) (0) | 2024.03.05 |
| 퀵 정렬(Quick Sort) (0) | 2024.03.04 |
