#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define MDN 254 // maks. dlugosc napisu
#define MN 20000 // maks il napisow

char **A,**B,**C;
int OP;

int countsort(char **A, int n ,int k)
{
int i, j, x;

int C[MDN];

for (i = 0; i <= k; i++)
   C[i] = 0;

  for (j = 0; j < n; j++){
   C[*(A[j]+x)] += 1;
   // teraz C[i] == iloœæ wartoœci równych "i" w tablicy A

  }
for (i = 1; i <= k; i++)
   C[i] += C[i-1];
   // teraz C[i] == iloœæ wartoœci mniejszych lub równych "i" w A


  for (j = 0; j < n; j++)
  {
    B[C[*(A[j]+x)]-1] = A[j];
    C[*(A[j]+x)] -= 1;
  }

    if (x == 0) {
  for (i = 0; i < n; i++)
     A[i] = B[i];

  }
  else {
   for (i = 0; i < n; i++)
     A[n-1-i] = B[i];

}

}


int radixsort(char **A, int n){

int i, j, x;

 int C[MDN];

 for (x = OP - 1; x >= 0; x--){

    countsort(A,n,MDN);


  }
   return 0;
 }



void drukuj(char **A,int n){
int i;
for (i=0;i<n;i++){
printf("%c %s",*(A[i]+1),A[i]);
printf("\n");
  }
}

void czytaj(char **A, int ilosc){
 char slowo[MDN];
 int i=0;
 int j=0;
 for (i=0;i<ilosc; i++){
    scanf("%s",slowo);
    A[i] = (char*) malloc(sizeof(char)*MDN);
    strcpy(A[i],slowo);
 }
}

void readfile(char **A, int ilosc){
 FILE *fp;
 fp = fopen("nazwiska.txt", "r");
 OP = 0;

 char slowo[MDN];
 int liczba;
 int i=0, j=0;
 for (i=0;i<ilosc; i++){
    fscanf(fp, "%i %s", &liczba, slowo);
    A[i] = (char*) malloc(sizeof(char)*MDN);
    if (OP < strlen(slowo)) OP = strlen(slowo);
    strcpy(A[i],slowo);
    for (j = strlen(slowo); j < MDN-1; j++) A[i][j] = 0;
 }
 fclose(fp);
}

void savefile(char **A, int n, char *nazwa_pliku)
{
 FILE *fp;
 fp = fopen(nazwa_pliku, "w+");
 int i;

 for (i = 0; i < n; i++)
   fprintf(fp, "%s\n", A[i]);

 fclose(fp);
}


main(){
  int n=MN;

    A=(char**) malloc(n*sizeof(char*));
    B=(char**) malloc(n*sizeof(char*));

readfile(A,n);
radixsort(A,n);
savefile(A,n,"wynik.txt");

}