Stable Radix Sort

A[0..N-1]들을 B[A[i]] 오름차순으로 정렬하여 C[0..N-1]에 넣는다. (B[A[i]]들은 0 이상 M 이하의 정수)

만약 B[A[i]]의 값이 같다면 A에서 먼저 나온 순서대로 넣는다.

#include <cstdio>

const int MAXM = 10;

int D[MAXM + 1];
void radixSort(const int *A, const int *B, int *C, int N, int M) {
	int i;
	for (i = 0; i <= M; i++) D[i] = 0;
	for (i = 0; i < N; i++) D[B[A[i]]]++;
	for (i = 1; i <= M; i++) D[i] += D[i - 1];
	for (i = N; i--; C[--D[B[A[i]]]] = A[i]);
}

int A[10] = { 5, 0, 3, 7, 4, 1, 9, 8, 2, 6 };
int B[10] = { 3, 4, 3, 2, 1, 1, 4, 2, 3, 1 };
int R[10];

int main() {
	int i;
	radixSort(A, B, R, 10, 4);
	for (i = 0; i < 10; i++) printf("%d %d %d\n", i, R[i], B[R[i]]);
}

with vector

#include <cstdio>
#include <vector>

using namespace std;

void radixSort(const vector<int> &A, const vector<int> &B, vector<int> &C, int N, int M) {
	int i;
	vector<int> D(M + 1, 0);
	for (i = 0; i <= M; i++) D[i] = 0;
	for (i = 0; i < N; i++) D[B[A[i]]]++;
	for (i = 1; i <= M; i++) D[i] += D[i - 1];
	for (i = N; i--; C[--D[B[A[i]]]] = A[i]);
}

vector<int> A({ 5, 0, 3, 7, 4, 1, 9, 8, 2, 6 });
vector<int> B({ 3, 4, 3, 2, 1, 1, 4, 2, 3, 1 });
vector<int> R(10);

int main() {
	int i;
	radixSort(A, B, R, 10, 4);
	for (i = 0; i < 10; i++) printf("%d %d %d\n", i, R[i], B[R[i]]);
}

with template

#include <cstdio>
#include <vector>

using namespace std;

template <typename _RanItA, typename _RanItB>
void radixSort(_RanItA _AFirst, _RanItA _ALast, _RanItB _B, _RanItA _C, int M) {
	_RanItA _A;
	int i;
	vector<int> D(M + 1, 0);
	for (i = 0; i <= M; i++) D[i] = 0;
	for (_A = _AFirst; _A != _ALast; _A++) D[_B[*_A]]++;
	for (i = 1; i <= M; i++) D[i] += D[i - 1];
	for (_A = _ALast; _A != _AFirst; _C[--D[_B[*_A]]] = *_A) _A--;
}

int A[10] = { 5, 0, 3, 7, 4, 1, 9, 8, 2, 6 };
char B[11] = "cdcbaadbca";
int R[10];

int main() {
	int i;
	radixSort(A, A + 10, B, R, 128);
	for (i = 0; i < 10; i++) printf("%d %d %d\n", i, R[i], B[R[i]]);
}