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

#define LEN 256

void free_array(char**, int);
void print_array(char**, int);
void quicksort(char**, int);
void swap(char**, char**);

void swap(char** a, char** b) {
    char* tmp = *a;
    *a = *b;
    *b = tmp;
}

void free_array(char** a, int n) {
    int i;
    for (i = 0; i < n; ++i)
        free(a[i]);
    free(a);
    return;
}

void print_array(char** a, int n) {
    FILE* fp;
    int i;
    fp = fopen("out.txt", "w");
    for (i = 0; i < n; ++i)
        fprintf(fp, "%s\n", a[i]);
    fclose(fp);
}

void quicksort(char** a, int n) {
    int k, i, j; char **t, *x;
    if (n < 1) return;
    while (n > 1) {
        x = a[0], i = -1, j = n;
        while (1) {
            do --j;
            while (strcmp(a[j], x) > 0);
            do ++i;
            while (strcmp(a[i], x) < 0);
            if (i < j)
                swap(a + i, a + j);
            else
                break;
        }
        if (j + 1 < n - j - 1) {
            ++j;
            n -= j;
            t = a;
            a += j;
        }
        else  {
            t = a + j + 1;
            j = n - j - 1;
            n -= j;
        }
        quicksort(t, j);
    }
}

int main(void) {
    int i, j, k, n = 0;
    char **a = NULL;
    char t[LEN];
    FILE* fp;

    fp = fopen("in.txt", "r");
    if (!fp) {
        return 1;
    }

    while (fscanf(fp, "%s", t) == 1) {
        if (!(a = (char**)realloc(a, (n + 1) * sizeof(char*)))) {
            free_array(a, n);
            fclose(fp);
            return 1;
        }
        for (j = 0; t[j]; ++j);
        if (!(a[n] = (char*)malloc(j + 1))) {
            free_array(a, n);
            fclose(fp);
            return 1;
        }
        for (k = 0; k <= j; ++k)
            a[n][k] = t[k];
        ++n;
    }

    quicksort(a, n);
    print_array(a, n);
    free_array(a, n);

    return 0;
}