//기수 정렬
//*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수), MaxNum : 배열에서 가장 큰 수
void Sort::RadixSort(int * Array, const int Length, int MaxNum)
{
int *store[10]; //각 자리수를 저장하는 공간
int rear[10]; //각 저장공간에서 가장 늦게 입력된 데이터의 위치
int radix; //어떤 큐에 데이터를 입/출력 할건지
지정하는 변수
int MaxMultiples = 1; //최대 자릿수
//저장 공간 초기화
for (int i = 0; i < 10;
i++)
{
store[i]
= new int[Length];
rear[i]
= -1;
}
//최대 자릿수 계산
while (MaxNum > 0)
{
MaxNum /= 10;
MaxMultiples
*= 10;
}
//정렬 시작
for (int multiples = 10;
multiples <= MaxMultiples; multiples *= 10)
{
//비교하고자 하는 자릿수를 구하기 위해 나눠야 하는 수
int div = multiples /
10;
//기수 별로 데이터 분류
for (int i = 0; i < Length; i++)
{
//기수 계산
radix
= Array[i] % multiples;
radix
/= div;
//구한 기수의 저장소에 데이터 저장
//데이터를 저장 할 수록 그 기수의 rear가
한칸씩 뒤로 밀린다.
store[radix][++rear[radix]]
= Array[i];
}
//데이터를 기수0 -> 기수9 순으로 순차적으로 입력
int index = 0;
for (radix = 0; radix
< 10; radix++)
{
//각 기수 순서대로 데이터 입력(각 기수 안에선 입력 받은 순으로 입력)
for(int i = 0; i <= rear[radix]; i++)
{
Array[index++] =
store[radix][i];
}
//입력이 완료된 기수의 rear는 -1로 초기화
rear[radix]
= -1;
}
}
//저장소의 메모리 해제
for (int i = 0; i < 10;
i++)
{
delete[] store[i];
store[i]
= NULL;
}
}
