// wskazowka do sortowania pozycyjnego
#include <time.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define MAX 60000l
#define MLD 1000000000.0 //10**9

#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 i, j, l, k = MDN;
int C[256];

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

  for (j = 0; j < n; j++){
   C[*(A[j]+l)] += 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]+l)]-1] = A[j];
    C[*(A[j]+l)] -= 1;
  }

    if (l == 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, l, k = MDN;
 int C[256];

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

    countsort(A,n);


  }
   return 0;
 }



void drukuj(char **A,int n){
  // drukuje  drugie litery napisow i napisy
  int i;
  for (i=0;i<n;i++){

    printf("%c %s",*(A[i]+1),A[i]);
//czyli   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");

}