기수정렬 (Radix Sort)

기수정렬이란

= 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘

   계수정렬과 유사하지만 더 많은 메모리를 차지하고 더 빠른 시간 복잡도를 가진다 ( 정렬횟수 X N)

 

구현시 주의할점

 

* 배열의 가장 큰 수를 찾아 정렬 반복회수를 구한다.

 

* 1의자리부터 10의 자리, 100의 자리 순서로 정렬을 진행한다.

 

* 계수정렬과 같이 0,1,2,3,4,5,6,7,8,9 정렬중인 버킷에 넣는 과정을 진행할때는 누적값을 함께 계산해야한다.

    (=> 해당 누적값이 추후 결과배열의 인덱스로 이용됨)

 

* 정렬의 반복은 배열의 최댓값이 더이상 나눠지지 않을때 (소수점으로 몫이 나올때) 까지 진행된다.

 

#define CRT_SECURE_NO_WARNING
#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX 99999

void RadixSort(int a[], int n)
{
	int div = 1;
	int max = 0;
	int i;
	for (i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
	}

	while (max / div > 0)
	{
		int bucket[10] = { 0, };
		int Result[MAX];

		for (i = 0; i < n; i++)bucket[a[i] / div % 10]++;
		for (i = 1; i < 10; i++)bucket[i] += bucket[i - 1]; //버킷 누적값 처리
		for (i = n - 1; i >= 0; i--)
		{
			Result[--bucket[a[i] / div % 10]] = a[i]; //버킷의 누적값을 정렬 시 인덱스로 이용
		}

		for (int i = 0; i < n; i++) a[i] = Result[i];
		div *= 10;
	}

}

int main()
{
	int i, n;

	cin >> n;
	int a[MAX];
	for (i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	RadixSort(a, n);

	for (i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}

 

구현에 크게 어려움이 있진 않다.

+) 나누는 값(div)의 자릿수가 증가함에 따라 추후 나눠지지 않는 수들이 어떻게 정렬되는지 이해가 어려울 수 있는데Result 배열에 들어가는 반복문이 어레이의 끝에서부터 시작한다는 점을 유의하고 직접 반복과정을 손으로 따라가면 이해가 쉬울 것이다.