// 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 max_dl 254


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


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

 char slowo[max_dl];
 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)*max_dl);
    if (max < strlen(slowo)) max = strlen(slowo);
    strcpy(A[i],slowo);
    for (j = strlen(slowo); j < max_dl-1; j++) A[i][j] = 0;
 }
 fclose(fp);
}

double sortuj_zliczenie(char **A, int n){
 struct timespec tp0, tp1;
 double Tn,Fn,x;

 clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp0);

 int i, j, l, k = max_dl;
 int C[256];

 for (l = max - 1; l >= 0; l--){
  for (i = 0; i <= k; i++)
   C[i] = 0;

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

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

  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];
  }
 }

 clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp1);
 Tn=(tp1.tv_sec+tp1.tv_nsec/MLD)-(tp0.tv_sec+tp0.tv_nsec/MLD);
 return Tn;
}

int sortuj_quicksort_partition(char **C, int p, int r)
{
 char* x = C[p];
 int i = p, j = r;
 char *t;
 while (1)
 {
  while (strcmp(C[j], x) > 0)
   j--;
  while (strcmp(C[i], x) < 0)
   i++;
  if (i < j)
  {
   t = C[i];
   C[i] = C[j];
   C[j] = t;
   i++;
   j--;
  }
  else return j;
 }
}

void sortuj_quicksort(char **C, int p, int r){
 if (p < r)
 {
  int q = sortuj_quicksort_partition(C, p, r);
  sortuj_quicksort(C, p, q);
  sortuj_quicksort(C, q+1, r);
 }
}

double sortuj_quick(char **C, int n)
{
 struct timespec tp0, tp1;
 double Tn,Fn,x;

 clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp0);

 sortuj_quicksort(C, 0, n-1);

 clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp1);
 Tn=(tp1.tv_sec+tp1.tv_nsec/MLD)-(tp0.tv_sec+tp0.tv_nsec/MLD);
 return Tn;
}

main(){
  int n=20000; //maksymalna dlugosc
  int j;
  FILE *fp, *fp2;
  // przez zliczenie
  A=(char**) malloc(n*sizeof(char*));
  B=(char**) malloc(n*sizeof(char*));

  // przez quicksort
  C=(char**) malloc(n*sizeof(char*));

  czytaj_z_pliku(A,n);
  czytaj_z_pliku(C,n);

  printf("Przez zliczenie: %lf s\n", sortuj_zliczenie(A,n));
  printf("Przez quicksort: %lf s\n", sortuj_quick(C,n));

  fp = fopen("nazwiska_zliczanie.txt", "w+");
  for (j = 0; j < n; j++)
  fprintf(fp, "%s\n", A[j]);

  fp2 = fopen("nazwiska_quicksort.txt", "w+");
  for (j = 0; j < n; j++)
  fprintf(fp, "%s\n", C[j]);

   fclose(fp);
    fclose(fp2);

}