반응형
기수 정렬이란?
기수 정렬 (Radix Sort)은 자리수를 비교하며 정렬을 진행하는 알고리즘 이다.
기수 정렬의 종류
1. LSD (Least Significant Digit) 방식의 정렬
- 가장 작은 자릿수부터 정렬을 진행 (숫자로 치면 일의 자리수부터)
- 가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이 MSD에 비해 간결하다
2. MSD (Most Significant Digit) 방식의 정렬
- 가장 큰 자릿수부터 정렬을 진행
- LSD와 비교했을 때 정렬 상태 확인등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다
기수 정렬의 과정
기수 정렬의 과정을 배열 [134,224,232,122] 을 이용해
LSD방식과 MSD방식으로 각각 설명하고자 한다.
1. LSD 방식
- 일의 자릿수부터 확인한다
- 숫자를 나타내는 버킷에 일의 자릿수를 확인하며 저장한다 (2는 버킷2에 / 4는 버킷4에)
- 꺼낼 때는 먼저 저장된 값부터 꺼내게 된다 (FIFO)
- 그 다음 자리수인 십의 자리를 기준으로 버킷에 저장한다
- 위의 과정과 동일하게 진행한다
- 그 다음 자리수인 백의 자리를 기준으로 버킷에 저장한다
- 마지막 자리수까지 검사를 마친 경우 오름차순으로 정렬이 완료된다
2. MSD 방식
- 가장 큰 자릿수 (여기서는 백의 자리)부터 확인한다
- 각 숫자를 나타내는 버킷에 백의 자릿수를 확인하며 저장한다
- 꺼낼 때는 먼저 저장된 값부터 꺼내게 된다 (FIFO)
- 두번째 과정부터는 STEP 1로 분류된 그룹끼리 정렬을 수행한다
(134,122) , (224,232)
<STEP 3>
- 두번째 그룹 (224,232)의 경우 자리수를 비교하지 않아도 이전에 정렬이 완료된 상태이므로
더 이상 정렬을 진행하지 않아도 된다
기수 정렬의 특징
- 정렬 순서상 앞과 뒤의 판단을 위한 비교 연산을 하지 않는다
- 정렬 대상의 모든 길이가 동일해야 가장 효율적이다
좋은 예시) [123,456,789,961], [music, clock, green, cream]
나쁜 예시) [4562,12,651,-1123],[blue, yellow, red] - 정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐(Queue)' 방식으로 저장 후 다시 꺼낸다
- 같은 수의 순서가 섞이지 않는 안정 정렬이다 (MSD 방식은 불안정 정렬)
시간복잡도
- 키의 수를 , 키의 최대 길이를 라고 했을 때, 시간복잡도는 이다.
공간 복잡도
- LSD 방식의 경우 키의 수를 , 버켓의 종류 수를 라고 했을 때, 공간복잡도는 이다.
- MSD 방식의 경우 키의 수를 , 버켓의 종류 수를 , 키의 최대 길이를 라고 했을 때, 공간복잡도는 이다.
코드로 구현한 기수 정렬
c++
void Radix_Sort() // 기수정렬 함수 !
{
int Radix = 1; // 최대 자릿수까지 계산을 하기 위한 변수
while (1) // 최대 자릿수가 몇 자리인지 알아내기 위한 반복문 !
{
if (Radix >= Max_Value) break; // Max_Value는 입력과 동시에 구해놓은 배열에서의 최댓값 !
Radix = Radix * 10;
}
for (int i = 1; i < Radix; i = i * 10) // 1의 자리부터 10씩 곱하면서 최대자릿수 까지 반복 !
{
for (int j = 0; j < MAX; j++) // 모든 배열을 다 탐색하면서
{
int K;
if (Arr[j] < i) K = 0; // 만약 현재 배열의 값이 현재 찾는 자릿수보다 작으면 0 !
else K = (Arr[j] / i) % 10; // 그게 아니라면 위에서 말한 공식 적용 !
Q[K].push(Arr[j]); // Queue배열에 해당 값을 순차적으로 저장 !
}
int Idx = 0;
for (int j = 0; j < 10; j++) // 0부터 9까지 Queue에 저장된 값들을 순차적으로 빼내기 위한 반복문.
{
while (Q[j].empty() == 0) // 해당 Index번호의 Queue가 빌 때 까지 반복
{
Arr[Idx] = Q[j].front(); // 하나씩 빼면서 배열에 다시 저장.
Q[j].pop();
Idx++;
}
}
}
}
코드 출처
Java
package Sort;
import java.util.Arrays;
// 기수 정렬 알고리즘 구현
public class radix {
// 배열에서 최대값을 얻기 위한 메서드
static int getMax(int[] data) {
int mx = data[0];
for(int i=1; i<data.length; i++) {
if(data[i] > mx) {
mx = data[i];
}
}
return mx;
}
// exp 변수의 수에 따라 숫자를 정렬
static void countSort(int[] data, int exp) {
int[] output = new int[data.length];
int[] count = new int[10];
Arrays.fill(count, 0);
// count 값 count배열에 저장
for(int i=0; i<data.length; i++) {
count[(data[i]/exp)%10]++;
}
// count 값이 포함시켜 count배열에 저장
for(int i=1; i<10; i++) {
count[i] += count[i-1];
}
// output배열 빌드
for(int i=data.length-1; i>=0; i--) {
output[count[(data[i]/exp)%10]-1] = data[i];
count[(data[i]/exp)%10]--;
}
// output 배열에 저장된 값을 data 배열에 저장
for(int i=0; i<data.length; i++) {
data[i] = output[i];
}
}
static void radixsort(int[] data) {
// 최대값 찾기
int m = getMax(data);
for(int exp=1; m/exp>0; exp*=10) {
countSort(data, exp);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] data = {4, 54, 2, 8, 63, 7, 55, 56};
// 기수 정렬 전
System.out.println("# 기수 정렬 전");
for(int i=0; i<data.length; i++) {
System.out.print(data[i]+" ");
}
System.out.println();
radixsort(data);
// 기수 정렬 후
System.out.println("# 기수 정렬 후");
for(int i=0; i<data.length; i++) {
System.out.print(data[i]+" ");
}
}
}
코드 출처
Python
def countingSort(arr, digit):
n = len(arr)
# 배열의 크기에 맞는 output 배열을 생성하고 10개의 0을 가진 count란 배열을 생성한다.
output = [0] * (n)
count = [0] * (10)
#digit, 자릿수에 맞는 count에 += 1을 한다.
for i in range(0, n):
index = int(arr[i]/digit)
count[ (index)%10 ] += 1
# count 배열을 수정해 digit으로 잡은 포지션을 설정한다.
for i in range(1,10):
count[i] += count[i-1]
print(i, count[i])
# 결과 배열, output을 설정한다. 설정된 count 배열에 맞는 부분에 arr원소를 담는다.
i = n - 1
while i >= 0:
index = int(arr[i]/digit)
output[ count[ (index)%10 ] - 1] = arr[i]
count[ (index)%10 ] -= 1
i -= 1
#arr를 결과물에 다시 재할당한다.
for i in range(0,len(arr)):
arr[i] = output[i]
# Method to do Radix Sort
def radixSort(arr):
# arr 배열중에서 maxValue를 잡아서 어느 digit, 자릿수까지 반복하면 될지를 정한다.
maxValue = max(arr)
#자릿수마다 countingSorting을 시작한다.
digit = 1
while int(maxValue/digit) > 0:
countingSort(arr,digit)
digit *= 10
arr = [ 170, 45, 75, 90, 802, 24, 2, 66]
#arr = [4, 2, 1, 5, 7, 2]
radixSort(arr)
for i in range(len(arr)):
print(arr[i], end=" ")
코드 출처
기수 정렬의 장단점
장점
- 키의 길이 가 작다면 의 시간으로 정렬을 할 수 있기 때문에 굉장히 빠른 속도로 정렬을 할 수 있다
- 카운팅 정렬과 같이 비교 연산 없이 정렬을 수행 할 수 있다
단점
- 추가적으로 버킷을 사용하기 때문에 데이터 크기에 비례한 메모리가 필요하다
- 버킷의 종류 (2진수,10진수,알파벳) 등이 고정적이지 않다
- 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용하기 힘들다
반응형
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 힙 정렬(Heap Sort) (1) | 2023.02.20 |
|---|---|
| [알고리즘] 퀵 정렬(Quick Sort) (0) | 2023.02.20 |
| [알고리즘] 병합정렬(Merge Sort) (0) | 2023.02.20 |
| [알고리즘] 삽입 정렬 (Insertion Sort) (0) | 2023.02.16 |
| [알고리즘] 버블 정렬(거품정렬, Bubble Sort) (1) | 2023.02.16 |