개념 요약
- 비교 없이 수행하는 정렬 알고리즘이다.
- 기수로는 정수, 낱말 등 다양한 자료로 사용 가능하지만 크기가 유한하며 사전 순으로 정렬할 수 있어야 한다.
- 기수에 따라 원소를 버킷에 집어넣기 때문에 비교 연산이 없다.
- 정수 같은 자료의 정렬 속도가 매우 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만 한 메모리가 필요하다.
- 부동소수점 실수처럼 특수한 비교 연산이 필요한 경우엔 사용하지 못한다.
- MSD(최상위 유효숫자)와 LSD(최하위 유효숫자) 방식이 있다.
- MSD
- 문자열이나 고정 길이 정수 표현 정렬에 전합니다.
- 가장 큰 자릿수부터 정렬을 진행한다.
- 중간에 정렬이 완료될 수 있다는 장점이 있지만 추가 작업이 필요하다.
- LSD
- 가장 작은 자릿수부터 정렬을 진행한다.
- MSD에 비해 간결하다.
정렬 과정
정수를 예로 과정 설명을 진행한다.
- 특정 자릿수가 정렬된 결과를 넣을 큐 A(0~9), 정렬된 결과를 넣을 임시 큐 B(0~9)을 선언한다.
- 원소를 차례대로 꺼내서 i번째 자리를 정렬하여 A에 넣는다.
- A에서 원소를 차례대로 꺼내서 i번째 자리를 정렬하여 B에 넣는다.( i = 1, i < 최대 자릿수)
- B에서 원소를 차례대로 꺼내서 A에 넣는다.
- 3~4를 반복한다.
- B에서 차례대로 원소를 꺼내서 원래 벡터에 초기화시킨다.
코드
int get_digit_num(int num, int i)
{
int d = std::pow(10, i);
return ((num / d) % 10);
}
int get_max_count(int max_elem)
{
int count = 0;
while (max_elem)
{
max_elem /= 10;
++count;
}
return (count);
}
void radix_sort(std::vector<int> &unsorted_array)
{
std::vector<std::queue<int>> A(10);
int max_elem = unsorted_array[0];
// 최댓값 구하기, 1의 자리 정렬해서 A에 넣기
for (int &elem : unsorted_array)
{
max_elem = (max_elem < elem ? elem : max_elem);
A[elem % 10].push(elem);
}
// 원래 벡터 초기화
unsorted_array.clear();
int temp = max_elem, count = get_max_count(max_elem);
// 1(10의 자리)부터 시작해서 최대 자릿수까지 진행
for (int idx = 1; idx < count; ++idx)
{
// 임시로 저장할 queue 생성
std::vector<std::queue<int>> B(10);
// 0~9까지 해당하는 큐 불러오기
for (int i = 0; i < 10; ++i)
{
// 해당 인덱스의 큐가 빌때까지 루프
while (A[i].empty() == false)
{
// 가장 앞의 원소를 자릿수 구분하여 넣어주기
int num = A[i].front();
B[get_digit_num(num, idx)].push(num);
A[i].pop();
}
}
// 기존 queue 초기화
A.clear();
// B를 그대로 A로 옮김
for (int i = 0; i < 10; ++i)
A.push_back(B[i]);
}
// 정렬이 완료된 큐벡터를 기존 벡터의 주소에 push
for (int idx = 0; idx < 10; ++idx)
{
while (A[idx].empty() == false)
{
unsorted_array.push_back(A[idx].front());
A[idx].pop();
}
}
}
시간 복잡도
- $O(d * n)$
- d는 정렬한 자릿수
장단점
- 문자열, 정수 정렬 가능하다.
- 자릿수가 없는 것은 정렬할 수 없고 중간결과를 저장할 메모리 공간이 필요하다.
'CS공부 > Algorithm' 카테고리의 다른 글
이분 탐색(Binary Search) (0) | 2022.06.22 |
---|---|
계수 정렬(Counting Sort) (0) | 2022.06.22 |
힙 정렬(Heap Sort) (0) | 2022.06.21 |
병합 정렬(Merge Sort) (0) | 2022.06.21 |
퀵 정렬(Quick Sort) (0) | 2022.06.20 |