#include <iostream>
using namespace std;

void print_array(int* array, int size)
{
	for (int i=0; i<size;  i++)
		cout << array[i] << " ";

	cout << endl;
}

// a modified version of quick sort. 
int partition(int* array, int low, int high, int digit)
{
	int x = array[high] % (digit * 10) / digit;
	int i, j;
	i = low - 1;
	for (j=low; j<=high-1; j++)
	{
		if ((array[j] % (digit * 10) / digit) <= x)
		{
			i++;
			swap(array[i], array[j]);
		}
	}

	swap(array[i+1], array[high]);
	return i+1;
}

void quick_sort_impl(int* array, int low, int high, int digit)
{
	if (low < high)
	{
		int q = partition(array, low, high, digit);
		quick_sort_impl(array, low, q-1, digit);
		quick_sort_impl(array, q+1, high, digit);
	}
}

void quick_sort(int* array, int size, int digit)
{
	quick_sort_impl(array, 0, size-1, digit);
}

void radix_sort(int* array, int size, int digits)
{
	// 从低位到高位依次排序
	int mul = 1;
	for (int i=0; i<digits; i++)
	{
		quick_sort(array, size, mul);
		mul *= 10;
	}
}

void main()
{
	int* array = 0;
	int size = 0;
	cout << "Input the size:";
	cin >> size;

	array = new int[size];
	for (int i=0; i<size; i++)
	{
		array[i] = rand()%9999;
	}

	print_array(array, size);
	radix_sort(array, size, 4);
	print_array(array, size);
}