/* malloc version */

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

#define MAXLINES 5000

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

#define MAXLEN 1000
int sneed_getline(char str[], int max);

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

  for (nlines = 0; (len = sneed_getline(line, MAXLEN)) > 0; nlines++) {
    if (nlines < max && (temp = malloc(len+1)) != NULL) {
      strcpy(temp, line);
      lineptr[nlines] = temp;
    } 
    
    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;
}