/*
	© MATTO MATTI 2018
	http://mattomatti.com/pl/fs23
	napisane przy użyciu Visual Studio Community 2015
	2018-03-29 v 1.0
*/

#include <iostream>
#include <vector>

using namespace std;

int mapuj(double a, double min) {
	while (a >= 10)
		a /= 10;
	return (int) a;
}

bool czywiekszy(double a, double b) {
	if (a < b)
		return czywiekszy(b, a);
	while (log10(a) > log10(b))
		b *= 10;
	return a > b;
}

void sortuj(double* dane, double n) {
	double min = dane[0], max = dane[0];
	for (int i = 1; i < n; i++) {
		if (dane[i] < min) {
			min = dane[i];
		}
		else if (dane[i] > max) {
			max = dane[i];
		}
	}
	int ilekoszy = ceil(max) - floor(min) + 1;
	vector< vector<double> > kosze;
	for (int i = 0; i < ilekoszy; i++) {
		vector<double> v;
		kosze.push_back(v);
	}
	for (int i = 0; i < n; i++) {
		int kosz = mapuj(dane[i], min);
		int q = 0;
		while (kosze[kosz].size() > q && czywiekszy(dane[i], kosze[kosz][q]))
			q++;
		kosze[kosz].insert(kosze[kosz].begin() + q, dane[i]);
	}
	int zapis = n - 1;
	for (int i = 0; i < ilekoszy; i++) {
		for (int j = 0; j < kosze[i].size(); j++) {
			dane[zapis--] = kosze[i][j];
		}
	}
}

int main() {
	int n;
	cout << "Podaj ilosc elementow: ";
	cin >> n;
	cout << "Podaj " << n << " elementow:\n";
	double* lista = new double[n];
	for (int i = 0; i < n; i++)
		cin >> lista[i];
	sortuj(lista, n);
	cout << "Posortowana lista to:\n";
	for (int i = 0; i < n; i++)
		cout << lista[i] << " ";
	delete lista;
	system("pause");
	return 0;
}