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

#define MAXLINES 5000
#define MAXLEN 1000
char line[MAXLINES][MAXLEN]; /* same as `char (line[MAXLEN])[MAXLINES]` */
/* we are using a lineptr here because array `line` pointer is const like all arrays and there addreses cant be changed to sort them only values can be exchanged
 * but copying each char back and forth would take up more resources  and using a lineptr is much more efficent, here we are not actully sorting line itself
 * but sorting pointers in lineptr to reflect the order*/
char *lineptr[MAXLINES]; /* same as `char *(lineptr[MAXLINES])` */

int readlines(char *lineptr[], int max);
void writelines(char *lineptr[], int max);
void my_qsort(char *lineptr[], int left, int right);

int 
main(void)
{
  int nlines;

  if ((nlines = readlines(lineptr, MAXLINES)) > 0) {
    my_qsort(lineptr, 0, nlines);
    writelines(lineptr, nlines);
    return 0;
  } else {
    printf("Err: lines, lines everywhere\n"); /* too much lines / input too big */
    return 1;
  }
  return 0;
}

int sneed_getline(char str[], int max);

int 
readlines(char *lineptr[], int max)
{
  int len, nlines;

  for (nlines = 0; (len = sneed_getline(line[nlines], MAXLEN)) > 0; nlines++) {
    if (nlines < max) {
      lineptr[nlines] = line[nlines];
    } 
    
    else
      return -1;
  }

  return nlines;
}

void 
writelines(char *lineptr[], int max)
{
  while (max--)
    printf("%s\n", *lineptr++);
}

int 
sneed_getline(char str[], int max)
{
  char input;
  char *str_og;

  str_og = str;

  --max;
  while (--max && (input = getchar()) != EOF && input != '\n')
    *str++ = input;

  /*
  if (input == '\n' && max)
    *str++ = input; */ 

  *str = '\0';

  return str - str_og;
}

void swap(char *lineptr[], int to, int from);

void 
my_qsort(char *lineptr[], int left, int right)
{
  int i, last;

  if (left >= right)
    return;

  swap (lineptr, left, (left+right)/2);

  last = left;

  for (i = left+1; i < right; i++)
    if (strcmp(lineptr[i], lineptr[left]) < 0)
      swap(lineptr, i, ++last);

  swap(lineptr, left, last);
  my_qsort(lineptr, left, last - 1);
  my_qsort(lineptr, last + 1, right);
}

void 
swap(char *lineptr[], int to, int from)
{
  char *temp;

  temp = lineptr[to];
  lineptr[to] = lineptr[from];
  lineptr[from] = temp;
}