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

#define MAXLEN 1000     /* max. duzina ulaznog reda */

#define MAXLINES 5000   /* max. redova za sortiranje */

char *lineptr[MAXLINES];	/* spoljasnji niz pokazivaca na redove teksta */
// ovaj niz je mogao biti i lokalni u main-u, ali bi tada stek morao
// biti dovoljno veliki da smesti MAXLINES * sizeof(char *)  bajtova
// za spoljasnju promenljivu se prostor obezbedjuje ranije!


int getline( char s[], int lim );
int readlines( char *lineptr[], int nlines);
void writelines( char *lineptr[], int nlines);
void qqsort( char *lineptr[], int left, int right );
void ispis( char *lineptr[], int i);
void swap(char *v[], int i , int j);


main()
 {
 	int nlines;         /* broj procitanih ulaznih redova */

	puts("\n\nUnesite linije teksta za sortiranje. Zavrsite sa ^Z");
    	if( (nlines = readlines(lineptr, MAXLINES)) >= 0 )
      {
		qqsort( lineptr, 0, nlines-1);
		writelines(lineptr, nlines);
	 	return 0;
	 }
    else
    {
	    printf("Greska: ulaz predugacak za sortiranje\n");
	    return 1;
	}
}

int readlines( char *lineptr[], int maxlines)     /* ucitavanje ulaznog reda */
{
	int len, nlines;
    	char *p, line[MAXLEN]; // line je pomocni bafer
    	nlines = 0;
    	while((len = getline(line, MAXLEN)) > 0 )
		if( nlines >= maxlines || (p = (char *) malloc(len)) == NULL)
	     	return -1;
	 	else
	 {
	     	line[len - 1] = '\0';      /* izbaci novi red */
	     	strcpy(p, line);
	     	lineptr[nlines++] = p;
	}
	return nlines;
}

/* unos linije i odredjivanje duzine  (sa '\0') */
int getline( char s[], int lim )
{  	int c, i;
	i = 0;
   	while( --lim > 0 && (c = getchar()) != EOF && ( c != '\n' ) )
     			s[i++] = c;

   	if( c == '\n' )
	s[i++] = c;
     s[i] = '\0';
   	return i;
}


// quick sort !!!
void qqsort( char *v[], int left, int right )
{
	int i, last;
	if(left >= right) return;
  	swap( v, left, (left+right)/2);
  	last = left;
  	for(i = left + 1; i <= right; i++)
      	if( strcmp(v[i], v[left]) < 0)     // poredjenje !
	  			swap(v, ++last, i);
  	swap( v, left, last);
  	qqsort( v, left, last-1);
  	qqsort( v, last+1, right);
}

void swap(char *v[], int i, int j)
{  char *temp;
   temp = v[i];
   v[i] = v[j];
   v[j] = temp;
}

/* ispis linija teksta */
void writelines(char *lineptr[], int nlines )
{
   int i=0;
   if (nlines) puts("sortirane linije\n");
   else puts("nije bilo linija na ulazu!");
   for(; i < nlines; i++) ispis(lineptr,i);

}

/* ispis izlaznog reda */
void ispis( char *lineptr[], int i)
{
	/* simulacija printf("%s\n", lineptr[i]);  */
  	int k;
     for( k = 0; k < strlen(lineptr[i]); k++)
		putchar( lineptr[i][k] );   // ispis znak po znak !!!
    printf("\n");
}