기수 정렬(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

리스트와 리스트 메소드



- 리스트

 앞에서 공부하면서 사용했던 리스트에 대해 알아보겠습니다. 리스트는 문자형처럼 시퀀스 자료형이지만 문자열과는 다르게 변경이 가능한 자료형입니다. 인덱싱, 슬라이싱, 연결, 반복, 멤버십 테스트 연산이 가능합니다.

 다음은 리스트의 추가, 삭제 예시입니다.

----------------------------------------------------------------------------------------

l1=range(10) # 0부터 9까지의 리스트 생성
print l1

del l1[2] # 2번째 인덱스 삭제
print l1

Sun,Mon,Tue,Wed,Thu,Fri,Sat=range(7) # 여러 변수에 한번에 리스트 생성 가능
print Sun,Mon,Tue,Wed,Thu,Fri,Sat
----------------------------------------------------------------------------------------
(실행 결과)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 3, 4, 5, 6, 7, 8, 9]
0 1 2 3 4 5 6
----------------------------------------------------------------------------------------

- 중첩 리스트
 중첩 리스트는 리스트를 인자로 가지는 리스트를 말합니다. 다음과 같이 사용합니다.
----------------------------------------------------------------------------------------
s=[2,3,4]
t=[1,s,5] # 리스트 s를 인자로 사용
print t
print t[1][1] # t리스트의 1번째 인덱스의 1번째 인덱스
----------------------------------------------------------------------------------------
(실행 결과)
[1, [2, 3, 4], 5]
3
----------------------------------------------------------------------------------------

- 리스트가 지원하는 메소드

 리스트가 지원하는 메소드는 아래와 같습니다. java와 메소드 이름이 비슷한 것 같습니다. 

1. append() : 리스트 마지막에 원소를 추가
문자열, 튜플, 사전도 추가가능
2. insert(위치,값) : 해당하는 인덱스의 위치에 원하는 값 추가
3. index(위치) : 해당하는 원소의 인덱스가 몇인지 반환
4. count(값) : 해당하는 값이 몇개가 존재하는지 반환
5. reverse() : 리스트의 순서를 뒤바꿔 줌(값 변경)
6. sort() : 리스트의 값을 정렬해서 값을 변경
7. remove(값) : 해당하는 값을 삭제하는데, 값이 여러개일 경우 첫 번째 값 삭제
8. extend(값) : 기존의 리스트에 값 자체를 추가(병합)

----------------------------------------------------------------------------------------
# append()
ap=[1,2,3,4]
ap.append(10) # 가장 뒤에 10 추가
print ap
print '*'*50

# insert()
ins=[1,2,4,5]
ins.insert(2,3) # 2번째 자리에 3 추가
print ins
print '*'*50

# index()
ind=[1,2,3,4,5,6]
print ind.index(3) # 3에 해당하는 인덱스 값 
print '*'*50

# count()
co=[1,2,3,2,2,2,7]
print co.count(2) # 2가 몇개인지
print '*'*50

# reverse()
re=[1,2,3,4]
re.reverse() # 순서를 거꾸로
print re
print '*'*50

# sort()
so=[11,-3,4,-50]
so.sort() # 정렬
print so
print '*'*50

# remove()
rem=[11,-3,4,-50,-3]
rem.remove(-3) # -3을 제거
print rem
print '*'*50

# extend()
s=[1,2,3,4]
t=[5,6,7]
s.extend(t) # s리스트에 t리스트를 추가(병합)
print s
# extend()와 append() 비교
s2=s.append(t) # append는 리스트 자체를 추가
print s2

----------------------------------------------------------------------------------------
(실행 결과)
[1, 2, 3, 4, 10]
**************************************************
[1, 2, 3, 4, 5]
**************************************************
2
**************************************************
4
**************************************************
[4, 3, 2, 1]
**************************************************
[-50, -3, 4, 11]
**************************************************
[11, 4, -50, -3]
**************************************************
[1, 2, 3, 4, 5, 6, 7]
----------------------------------------------------------------------------------------

- 리스트를 스택, 큐로 이용

 스택은 후입선출 구조, 큐는 선입선출 구조를 가집니다. 리스트의 메소드를 이용해서 스택과 큐처럼 사용할 수 있습니다. append()메소드와 pop()메소드를 이용합니다. pop()메소드는 기본적으로 마지막 원소를 꺼내고, 인자안에 인덱스를 적어주면 해당하는 인덱스의 값을 꺼냅니다.
----------------------------------------------------------------------------------------
# stack
s=[10,20,30,40,50]
s.append(60)
print s
print s.pop()
print s
print s.pop()
print s
print '*'*50

# queue
q=[10,20,30,40,50]
q.append(60)
print q
print q.pop(0)
print q
print q.pop(0)
print q
----------------------------------------------------------------------------------------
(실행 결과)
[10, 20, 30, 40, 50, 60]
60 # 가장 마지막 원소인 60을 꺼냄
[10, 20, 30, 40, 50]
50 # 가장 마지막 원소인 50을 꺼냄
[10, 20, 30, 40]
**************************************************
[10, 20, 30, 40, 50, 60]
10 # 가장 앞의 원소인 10을 꺼냄
[20, 30, 40, 50, 60]
20 #가장 앞의 원소인 20을 꺼냄
[30, 40, 50, 60]
----------------------------------------------------------------------------------------

* 출처 : 한국기술교육대학교 온라인평생교육원 파이썬프로그래밍



저작자표시 비영리

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

[파이썬] 튜플과 집합자료형  (0) 2017.02.14
[파이썬] 리스트 활용  (4) 2017.02.07
[파이썬] 문자열 메소드와 포멧팅  (2) 2017.02.03
[파이썬] 문자열 정의 및 기초연산  (0) 2017.02.01
[파이썬] 제어문과 함수  (0) 2017.01.25

+ Recent posts

티스토리툴바