#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXLINES 5000 /* максимальное число строк */
char *lineptr[MAXLINES]; /* указатели на строки текста */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qqsort(void *lineptr[], int left, int right,int (*comp)(void *, void *));
char *allloc(int n);
int numcmp(char *, char *);
int getline(char *s, int lim);
/* сортировка строк */
main(int argc, char *argv[])
{
    int nlines; /* количество прочитанных строк */
    int numeric = 0; /* 1, если сорт. по числ. знач. */
    if (argc > 1 && strcmp(argv[1], "-n") == 0)
        numeric = 1;
    if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        qqsort((void **) lineptr, 0, nlines-1,(int (*)(void*,void*))(numeric ? numcmp : strcmp));
        writelines(lineptr, nlines);
        return 0;
    } else {
        printf("Bведено слишком много строк\n");
        return 1;
    }
}

#define MAXLEN 1000

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

    nlines = 0;
    while ((len = getline(line, MAXLEN)) > 0)
        if (nlines >= maxlines || (p = allloc(len)) == NULL)
            return -1;
        else {
            line[len-1] = '\0'; /* убираем символ \n */
            strcpy(p, line);
            //printf("%d\n",line);
            //printf("%d",p);
            lineptr[nlines++] = p;
        }
    return nlines;
}

void qqsort(void *v[], int left, int right, int (*comp)(void *, void *))
{
    int i, last;
    void swap(void *v[], int, int);
    if (left >= right) /* ничего не делается, если */
        return; /* в массиве менее двух элементов */
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left+1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qqsort(v, left, last-1, comp);
    qqsort(v, last+1, right, comp);
}

/* numcmp: сравнивает s1 и s2 как числа */
int numcmp(char *s1, char *s2)
{
    double v1, v2;
    v1 = atof(s1);
    v2 = atof(s2);
    if (v1 < v2)
        return -1;
    else if (v1 > v2)
        return 1;
    else
        return 0;
}

void writelines(char *lineptr[], int nlines)
{
    int i;
    for (i = 0; i < nlines; i++)
        printf("%s\n", lineptr[i]);
}

#define ALLOCSIZE 10000 /* размер доступного пространства */
static char allocbuf[ALLOCSIZE]; /* память для alloc */
static char *allocp = allocbuf; /* указатель на своб. место */
char *allloc(int n) /* возвращает указатель на n символов */
{
    if (allocbuf + ALLOCSIZE - allocp >= n) {
        allocp += n; /* пространство есть */
        return allocp - n; /* старое p */
    } else /* пространства нет */
        return 0;
}

int getline(char *s, int lim)
{
    int c, i;
    for (i = 0; i < lim-1 && (c = getchar()) != EOF && c != '\n'; ++i)
        s[i] = c;
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    s[i] = '\0';
    return i;
}
void swap(void *v[], int i, int j)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}