[알고리즘] Radix Sort 기수정렬

0.

기수정렬은 자료구조 "큐"를 활용하는 알고리즘이다.

 

 

1.

아주 단순하게 말하자면

정렬할 숫자들을 일의 자리 10의 자리 각 자릿 수를 기준으로 하여 큐배열에 넣고 순서대로 빼내는 과정이다.

과정을 모두 거치면 자연스럽게 정렬되어 있다.

 

위 과정을 거치기 위해서는 "큐"를 구현할 줄 알아야한다.

큐를 복습하자.

 

 

 

[Remark](복습이라서 대충 설명)

큐: 선입선출 자료구조, 먼저 들어간 사람이 먼저 나온다.

 

스택에서 배운 push와 pop과 마찬가지로 큐에서도 Dequeue, Enqueue가 있다.

(tip.스택은 push와 pop이 이루어지는 곳이 같은 반면, 큐는 enqueueu와 dequeueu가 이루어지는 위치가 다르다.)

 

Queue ADT(abstract data type = 자바의 interface와 비슷한 개념)

 

1)void QueueInit(Queue * pq)

초기화

 

2)int QIsEmpty(Queue *pq)

비었다면 1(true), 아니면 0

 

3)void Enqueue(Queue *pq, Data data)

데이터 삽입

 

4)Data Dequeue(Queue *pq)

데이터 삭제 후, 반환

 

5)Data Qpeek(Queue *pa)

데이터를 삭제하지 않고, 반환 -> 확인용

 

 

Enqueue를 사용하기 위해서 front변수 이용, dequeue를 사용하기 위해서 rear을 이용한다.

 

 

그런데, 문제점이 있다 아래 그림 상황에서는 2개의 공간이 낭비되고 있다.

 

 

 

이를 해결하기 위해서 원형큐를 이용한다.

그런데 여기서 또 문제점이 발생한다

 

 

 

이를 해결하기 위해서 배열의 길이가 n일때 n개를 모두 채우는 것이 아니라 n-1개만 채워도 다 채운 것으로 인식한다.

 

따라서 우리는 아래와 같은 2가지를 알 수 있다.

 

1)원형 큐가 텅 빈 상태 = f와 r이 동일한 위치를 가리킨다.

2)원형 큐가 꽉 찬 상태 = r이 가리키는 위치의 앞을 f가 가리킨다.

 

배열 기반의 큐(=바로 위에서 배운 원형 큐)와 연결리스트 기반의 큐를 구현해보자

 

1.배열기반의 큐

 

1.헤더파일

 

2. CircularQueue.c

 

3.main.c

 

 

 

2.연결리스트기반의 큐

 

1.헤더파일

배열기반과 다르게 node구조체를 구현했고 Queue는 배열을 없애고 f,r 노드포인터로 노드들을 관리하기 시작했다.

 

 

2.ListBaseQueue.c

 

 

3.main.c

 

 

 

 

자 이제 큐도 구현했으니 기수정렬을 사용해보자.

 

 

( 1 ) 큐배열과 정렬이 필요한 배열을 준비한다.

 

( 2 ) 큐배열을 우선 초기화를 해주자

 

( 3 ) 각 자릿수가 기준이 되어 정렬되므로 자릿 수가 기준이 되는 반복문을 크게 두자. -> pos, max_len변수이용

 

( 4 ) 배열을 돌리는 index = di, 버킷(큐배열)을 돌리는 index = bi, 기수 = radix, divfac

 

( 5 ) 자릿수를 나눠주면서 나눠진 결과를 기준으로 각 큐배열에 넣어준다.

 

( 6 ) 큐배열에 모두 넣었으면, 다시 원래 배열에 처음부터 넣어준다.

 

[code]