기수 정렬
기수 정렬은 비 비교 정렬 알고리즘입니다. 이 알고리즘은 기수에 따라 버킷에 요소를 삽입하여 비교를 방지합니다(Radix / Base는 숫자를 나타내는 데 사용되는 고유 한 자릿수입니다. 예를 들어 10 진수는 10 개의 고유 한 자릿수를 가짐). 개별 요소의 자릿수를 기준으로 요소를 정렬합니다. 최하위 자릿수에서 최상위 자릿수까지 숫자에 대한 계수 정렬을 수행합니다. 버킷 정렬또는 디지털 정렬이라고도하며 병렬 머신에서 매우 유용합니다.
기수 정렬 알고리즘
n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.
-
배열에서 가장 큰 요소
maxm을 찾습니다. -
안정적인 정렬 알고리즘을 사용하여 최하위부터 시작하여
maxm의 각 숫자를 정렬합니다.
기수 정렬 예
(1851, 913, 1214, 312, 111, 23, 41, 9)배열이 있다고 가정합니다. 기수 정렬 알고리즘을 사용하여 정렬합니다.
| 인덱스 | 입력 배열 | 첫 번째 반복 | 두 번째 반복 | 세 번째 반복 | 네 번째 반복 |
|---|---|---|---|---|---|
| 0 | 1851 | 1851 | 0009 | 0009 | 0009 |
| 1 | 0913 | 0111 | 0111 | 0023 | 0023 |
| 2 | 1214 | 0041 | 0312 | 0041 | 0041 |
| 3 | 0312 | 0312 | 0913 | 0111 | 0111 |
| 4 | 0111 | 0913 | 1214 | 1214 | 0312 |
| 5 | 0023 | 0023 | 0023 | 0312 | 0913 |
| 6 | 0041 | 1214 | 0041 | 1851 | 1214 |
| 7 | 0009 | 0009 | 1851 | 0913 | 1851 |
첫 번째 반복에서는 단위 위치에 따라 정렬 한 다음 수십, 수백, 수천 위치로 이동하여 최종 정렬 된 배열을9, 23, 41, 111, 312, 913, 1214, 1851로 얻습니다.
기수 정렬 알고리즘 구현
#include <iostream>
using namespace std;
const int N = 10;
int maxm(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
void countingSort(int arr[], int n, int place) {
int output[n];
int count[N];
for (int i = 0; i < N; ++i) count[i] = 0;
for (int i = 0; i < n; i++) count[(arr[i] / place) % 10]++;
for (int i = 1; i < N; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / place) % 10] - 1] = arr[i];
count[(arr[i] / place) % 10]--;
}
for (int i = 0; i < n; i++) arr[i] = output[i];
}
void radixsort(int arr[], int n) {
int max = maxm(arr, n);
for (int place = 1; max / place > 0; place *= 10) countingSort(arr, n, place);
}
int main() {
int n = 5;
int arr[5] = {1851, 913, 1214, 312, 111};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
radixsort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
기수 정렬 알고리즘 복잡성
시간 복잡성
- 평균 사례
기수 정렬의 시간 복잡도는 O(n + b)이며 여기서 b는 입력 범위입니다. 최대 요소maxm에d 자리가 있으면 기수 정렬의 시간 복잡도는O(d * (n + b))가됩니다. d와 b는 일반적으로 작기 때문에 시간 복잡도는 [Big Theta] :O(n)정도입니다.
- 최악의 경우
최악의 시간 복잡도는 [Big O] :O(n)입니다.
- 베스트 케이스
최적의 시간 복잡도는 [Big Omega] :O(n)입니다. 최악의 시간 복잡성과 동일합니다.
공간 복잡성
기수 정렬 알고리즘의 공간 복잡도는O(n + b)이며 여기서b는 입력 범위입니다. 기수 정렬의count &output 배열에서 비롯됩니다. 때로는 b가 n보다 클 수있어 복잡성이 비선형이됩니다.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn