기수정렬 ( Radix Sort )

기수 정렬은 기수 별로 비교 없이 수행하는 정렬 알고리즘이다. 기수로는 정수, 낱말, 천공카드 등 다양한 자료를 사용할 수 있으나 크기가 유한하고 사전순으로 정렬할 수 있어야 한다. 버킷 정렬의 일종으로 취급되기도 한다. 위키백과

• 전체 키를 여러 자리로 나누어 각 자리마다 계수 정렬과 같은 안정적 정렬 알고리즘( 계수정렬, 삽입정렬, 합병정렬 등)을 적용해 정렬하는 바업
• 낮은 자리부터 순차적 정렬
• 낮은 자리수부터 비교해 정렬해가는 것이 기본 개념인 정렬 알고리즘
• 비교연산 X
• 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요

[예시]

성능

• 제자리 정렬 X ( 진법 크기 만큼의 메모리가 추가됨) 경우에 따라서는 데이터 크기만큼의 메모리 추가
• 안정된 정렬 : 순서대로 뒤쪽 레코드부터 가장 뒤쪽에 배치
• 평균 시간 복잡도 = $O(dn)$
• 최악 시간 복잡도 = $O(dn)$
• 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);
}

버킷정렬( Bucket Sort )