#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

/*
	return 0 if there is no character on declared position
	returns 1 for a, 2 for b etc.
*/
int characterNumber(string number, int position) {
	if(position >= number.length()) return 0;
    return (int)(number[position] - 'a'+1);
}
void sortByPosition(string tab[], int n, int pos) {
	int k = 'z'-'a'+2; //+2 , bo oddzielnie traktuje a i NULL (0)
    int *counters = new int[k];
    string *result = new string[n];
    for(int i=0; i<k; i++) counters[i] = 0;
    for(int i = 0; i < n; i++) counters[characterNumber(tab[i], pos)]++;
    for(int i=1; i<k; i++) counters[i] += counters[i-1];
    for(int i=n-1; i>=0; i--) {
    	result[--counters[characterNumber(tab[i], pos)]]=tab[i];
    }

    for(int i = 0; i < n; i++) tab[i]=result[i];

    delete [] counters;
    delete [] result;
}
void radixSort(string tab[], int n) {
	int maxLength = tab[0].length();
	for(int i = 1; i < n; i++)
		if(tab[i].length() > maxLength) maxLength = tab[i].length();

    for(int i = maxLength-1; i >= 0; i--){
    	sortByPosition(tab, n, i);
	}
}

int main() {
	int n = 6;
	string strings[n];
	strings[0] = "abecadlo";
	strings[1] = "da";
	strings[2] = "aaa";
	strings[3] = "aa";
	strings[4] = "aaaa";
	strings[5] = "baca";
	radixSort(strings,n);

	for(int i = 0; i < n; i++){
		cout << strings[i] << endl;
	}
}