[알고리즘] 기수 정렬
기수 정렬
계수 정렬Counting Sort
와 마찬가지로 비교를 하지 않아요.
데이터를 구성하는 요소의 기수Radix
를 활용해서 정렬을 진행합니다. 정수를 정렬한다 가정하면 첫째 자리수를 기준으로 정렬 -> 둘째 자리수를 기준으로 정렬 -> ... 이렇게 반복해서 정렬을 하는 알고리즘이죠.
특징
시간 복잡도는 O(d * (n + b))
이고, d
는 정렬할 숫자의 자릿수, b
는 10입니다(각 자릿수의 범위는 0~9니까요).
기수 정렬의 경우 문자열이나 정수는 정렬이 가능하지만, 자릿수가 없는 것은 정렬할 수가 없습니다(실수가 대표적이죠). 계수 정렬처럼 중간 결과를 저장할 배열이 필요해 In-place
하지 않습니다.
소스
큐Queue
또는 계수 정렬Counting Sort
를 활용할 수 있는데, 이번엔 계수 정렬Counting Sort
를 활용해 구현해보도록 할게요.
#include <vector>
#include <limits.h>
using namespace std;
class RadixSort
{
public:
static void sort(vector<int>& arr)
{
int maxValue = getMax(arr);
for(int exp = 1; maxValue / exp > 0; exp *= 10)
countingSort(arr, exp);
}
private:
static void countingSort(vector<int>& arr, int exp)
{
vector<int> buffer(arr.size());
vector<int> counting(10);
for(int i = 0 ; i < arr.size(); ++i)
counting[(arr[i] / exp) % 10]++;
for(int i = 1 ; i < counting.size(); ++i)
counting[i] += counting[i - 1];
for(int i = arr.size() - 1; i >= 0 ; --i)
buffer[--counting[(arr[i] / exp) % 10]] = arr[i];
arr = buffer;
}
static int getMax(const vector<int>& arr)
{
int ret = INT_MIN;
for(const int& a : arr)
{
if(ret < a)
ret = a;
}
return ret;
}
};
추가
위에 제가 구현한 코드는 LSDLeast-significant-digit
방식으로, 가장 낮은 자리수부터 전개를 합니다. 가장 높은 자리수부터 시작하는건 MSDMost-significant-digit
라고 해요.
MSD의 경우 정렬을 수행하는 과정에서 이미 정렬이 완료되어, 끝까지 수행해야 하는 LSD보다 효율적이에요(ex. 10004와 70002의 비교).
하지만, 그럴려면 한번 기수 정렬을 수행하고 체크 처리를 해야하는데다, 구현은 LSD가 용이하기 때문에 주로 LSD가 언급이 됩니다.
Author And Source
이 문제에 관하여([알고리즘] 기수 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@redgem92/알고리즘-기수-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)