52. 기수 정렬

기수 정렬이란?

기수 정렬은 비교 정렬이 아닌 정렬 알고리즘 중 하나로, 정렬할 요소들을 자릿수별로 비교하여 정렬하는 방법이다.

기수 정렬은 요소들을 자릿수별로 그룹화하고 정렬하는 방식으로 동작하며, 작은 자릿수부터 큰  자릿수까지 반복하여 정렬을 수행한다.

 

동작 방식

1. 정렬할 요소들을 가장 낮은 자릿수부터 가장 높은 자릿수까지 반복하여 처리한다.

2. 각 자릿수에 대해 요소들을 그 자릿수를 기준으로 그룹화한다.

3. 가장 낮은 자릿수부터 시작하여 요소들을 해당 버킷에 배치한다.

4. 버킷에 배치된 요소들을 순서대로 가져와 정렬된 순서로 재배치한다.

5. 모든 자릿수에 대한 처리가 완료될 때까지 위 과정을 반복한다.

 

동작 방식만 보면 쉽게 이해하기 어려울 수 있다. 코드를 보고 직접 구현하면서 이해하는 것이 가장 바람직한 것 같다.

---

// 기수 정렬 
void RadixSort(int User_Data[], int n){
	listPointer first = NULL;
	first = Create_List(first, n);
	
	//listPrint(first);
	first = radix_Sort(first);
	listtoArray(first, User_Data, n);
}
// 기수정렬 알고리즘 
listPointer radix_Sort(listPointer temp){
	int i, j, digit;
	listPointer front[RADIX_SIZE], rear[RADIX_SIZE];
	
	// 자리수만큼의 반복을 실행하는데 배열 인덱스때문에 자리수-1부터 0까지 진행 
	for(i=MAX_DIGIT-1;i>=0;i--){
		// front와 rear를 생성하여 초기화 시켜준다. 
		for(j=0;j<RADIX_SIZE;j++)
			front[j] = rear[j] = NULL;
		
		// 해당 자리의 기수위치에 노드를 옮겨둔다. 
		for(;temp;temp=temp->link){
			digit = temp -> key[i];
			if(!front[digit]) front[digit] = temp;
			else rear[digit] -> link = temp;
			rear[digit] = temp;
		}
		
		// 옮겨둔 노드를 링크드 리스트로 변환시킨다. 
		temp = NULL;
		for(j=RADIX_SIZE-1; j>=0; j--)
			if(front[j]){
				rear[j] -> link = temp;
				temp = front[j];
			}
	}
	return temp;
}