기수 정렬(Radix Sort)



기수정렬?

기수정렬은 자리수별로 비교하여 정렬하는 방법입니다.


비교연산은 하지않고, 정수와 같은 자료의 정렬 속도가 매우 빠릅니다.


복잡도

가장 큰 숫자의 자리수가 d라고할 때 복잡도는 아래와 같습니다.




아래와 같은 배열이 있을 때 


가장 큰 숫자의 자리수는 3이므로 정렬을 3번 진행합니다.


각 자리수에 해당하는 큐에 순서대로 데이터를 삽입합니다.


가장먼저 1의자리 정렬입니다.



1의자리를 기준으로 정렬된 데이터를 

10의자리 기준으로 정렬합니다.



마지막으로 10의자리 기준으로 정렬된 데이터를

100의자리 기준으로 정렬합니다.


정렬한 데이터를 큐에서 전부 꺼내주면 정렬이 완료됩니다.


큐를 이용한 기수 정렬 예제


많은 예제들을 찾아봤는데, 0~9 총 10개의 큐를 만들어서 진행하는 예제가 많았습니다.


굳이 10개의 큐가 필요할까? 라는 생각을 하게 되었고, 큐 하나만 이용해서 정렬을 진행해 봤습니다.



Queue put(),get()함수 


Queue관련 내용은 생략하겠습니다.


Queue관련 내용은 아래 포스팅 참고바랍니다.


[Data Strcuture] 큐(Queue)



#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;
}
}

// ARRAY
void print_array(int array[], int size){
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n");
}


기수정렬 함수


가장 큰 숫자를 찾아서 자리수를 구한 뒤


0~9까지 각 자리에 맞는 숫자가 나올때 큐에 삽입하고


반복이 끝나면 큐에서 배열에 담고 큐를 초기화 하는 방법으로 진행 했습니다.


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 print_array(int array[], int size){
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n");
}


실행 함수


void main(){
int array[] = {11,1,83,202,55,4,119,81,15,47,19,28};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
radix_sort(array, size);
}


실행 결과



참고 : 위키백과(기수 정렬)



관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 합병 정렬(Merge Sort)  (0) 2019.05.04
[C] 힙 정렬(Heap Sort)  (0) 2019.05.01
[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20

큐(Queue)


큐(Queue)?

큐는 FIFO(First In First Out)구조로 가장 먼저 들어간 값이 가장먼저 나오는 구조입니다.


삽입하는 put 동작과 삭제하는 get 동작이 있습니다.


front(앞)에서 값을 얻어내고, rear(뒤)에 값을 넣습니다.


1. 큐 형태


2. 큐 종류


큐의 종류는  선형 큐, 원형 큐, 우선순위 큐 등이 있습니다.


- 선형 큐(Linear Queue) : 기본적인 큐의 형태로 막대모양의 큐로 빈 공간 사용 시 모든 자료를 꺼내거나 옮겨야 한다는 단점이 있음

- 원형 큐(Circular Queue) : 선형큐의 단점을 보완하는 구조로 front와 rear가 연결된 형태

- 우선순위 큐(Priority Queue) : 데이터 삽입 시 우선순위에 따라 정렬 후 저장하는 방식



배열을 이용한 원형 큐 예제


원형큐의 경우 front, rear 구분을 위한 공간이 하나 필요합니다.

그래서, 크기가 10인 큐의 경우 사용가능한 공간은 9가 됩니다.


큐로 사용할 int형 배열 선언 및 초기화 함수


#include "stdio.h"
#define MAX 10

int queue[MAX];
int front, rear;

void init_queue(){
front = rear = 0;
}


초기화 함수


front와 rear값을 같게하면 초기화 가능


void clear_queue(){
front = rear;
}


put 함수


(rear+1) % 큐 크기 == front 일 경우 오버 플로우 발생


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;
}


원형큐는 아래 그림과 같이 모듈러를 생각하면 편합니다.

get 함수


front와 rear가 같을 경우 빈 값이므로 언더플로우 발생


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 print_queue(){
printf("\n");
for(int i=front; i!=rear; ++i % MAX){
printf("queue[%d]=%d\n",i,queue[i]);
}
if(front == rear){
printf("queque is empty!!! \n");
}
printf("\n");
}

메인함수

큐의 크기가 10이므로 10번째 값을 넣을때에 오버플로우가 발생하고,
10번째 값을 가져올 때에는 언더플로우가 발생합니다.

void main(){
init_queue();
put(1);
put(3);
put(6);
put(9);
put(7);
put(2);
put(0);
put(0);
put(10);
put(20); // 10번째 값
printf("################################################################\n");
print_queue();
for(int i=0; i<3; i++){
get();
}
printf("################################################################\n");
print_queue();
for(int i=0; i<7; i++){
get();
}
printf("################################################################\n");
put(0);
put(0);
put(10);
clear_queue();
print_queue();
}

실행결과


참고 : C로 배우는 알고리즘 (이재규)




저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 스택(Stack)  (1) 2019.03.29
[C] 연결리스트(LinkedList)  (0) 2019.03.28

+ Recent posts

티스토리툴바