기수정렬 ( Radix Sort )
기수 정렬은 기수 별로 비교 없이 수행하는 정렬 알고리즘이다. 기수로는 정수, 낱말, 천공카드 등 다양한 자료를 사용할 수 있으나 크기가 유한하고 사전순으로 정렬할 수 있어야 한다. 버킷 정렬의 일종으로 취급되기도 한다. 위키백과
•
전체 키를 여러 자리로 나누어 각 자리마다 계수 정렬과 같은 안정적 정렬 알고리즘( 계수정렬, 삽입정렬, 합병정렬 등)을 적용해 정렬하는 바업
•
낮은 자리부터 순차적 정렬
•
낮은 자리수부터 비교해 정렬해가는 것이 기본 개념인 정렬 알고리즘
•
비교연산 X
•
정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요
[예시]
성능
•
제자리 정렬 X ( 진법 크기 만큼의 메모리가 추가됨)
경우에 따라서는 데이터 크기만큼의 메모리 추가
•
안정된 정렬 : 순서대로 뒤쪽 레코드부터 가장 뒤쪽에 배치
•
평균 시간 복잡도 =
•
최악 시간 복잡도 =
•
d : 키 값의 해당 진법에서의 자리 개수
구현 ( 수업에선 안다룸 )
#include <stdio.h>
#define MAX 20
// QUEUE
int queue[MAX];
int front, rear = 0;
int put(int k){
if((rear+1) % MAX == front){
printf("QUEUE OVER FLOW!\n\n");
return -1;
}else{
queue[rear] = k;
rear = ++rear % MAX;
return 1;
}
}
int get(){
int k;
if(front == rear){
printf("QUEUE UNDER FLOW!\n\n");
return -1;
}else{
k = queue[front];
front = ++front % MAX;
return k;
}
}
void radix_sort(int array[], int size){
int max = array[0];
int digit = 0;
int factor = 1;
for(int i=1; i<size; i++){
if(max<array[i]) max = array[i];
}
for(int i=max; i>0;i/=10){
digit++;
}
for(int i =0; i<digit; i++){
for(int j=0; j<10; j++){ // 0~9
for(int k=0; k<size; k++){
if((array[k]/factor)%10==j){
put(array[k]);
}
}
}
factor *=10;
for(int i=front; i!=rear; i++){
array[i] =get();
}
printf("########### %d ROUND ###########\n",i+1);
print_array(array,size);
front=rear=0;
}
}
void main(){
int array[] = {11,1,83,202,55,4,119,81,15,47,19,28};
int size = sizeof(array)/sizeof(int);
radix_sort(array, size);
}
C
복사
버킷정렬( Bucket Sort )
버킷 정렬, 버킷 소트는 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다. 버킷은 빈이라고도 불리고, 버킷 정렬도 빈 정렬로도 불린다. 각 버킷은 다른 정렬 알고리즘을 사용하거나 버킷 정렬을 반복 적용해 각각 정렬한다. 분포 정렬이고 일반화된 비둘기집 정렬과 같다. 위키백과
•
분석 대상 데이터의 분포 특성을 활용해 계산 복잡성을 수준으로 개선
•
데이터가 특정 작은 범위 내에서만 변화하는 경우 (ex. [1, k]) 그리고 해당 범위 내에서 확률적으로 균등히 분포된 경우 사용
[예시]
A의 분포가 균등하다면 각 버킷에는 1~2개만 존재하겠죠?
그러면 버킷 하나를 정렬하는데에는 이 될 것이고 (보통 퀵 정렬 진행)
이 작업을 n개의 버킷에 수행한다면 복잡도는 이 될 것이에요
•
데이터 n개가 주어졌을 때 데이터의 범위를 n개로 나누고 이에 해당하는 n개의 버킷을 만든다.
•
각각의 데이터를 해당하는 버킷에 집어 넣는다. (C 등에서는 연결리스트를 사용하며 새로운 데이터는 연결리스트의 head에 insert한다)
•
버킷별로 정렬한다.
•
이를 전체적으로 합친다.
구현
[pseudo code]
BucketSort (int A[ ], int n)
/* 입력 : 정렬할 배열 A, 크기 n
단, 배열 A 원소값 [0,1]
출력 : 정렬된 배열 A*/
{
for (i = 1; i <= n; i++)
A[i]를 리스트 T[ nA[i] ]에 삽입;
for (i = 0; i <= n – 1; i++)
삽입 정렬에 의해 리스트 T[i]를 정렬한다;
리스트 T[0], T[1],……,T[n–1]을 하나로 묶는다;
}
C
복사
