DNA Sorting

Description

One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.

Input

The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output

Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. Since two strings can be equally sorted, then output them according to the orginal order.

Sample Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
struct DNA{
    char str[51];
    int num;
    struct DNA *next;
};
struct DNA *InitLink(struct DNA *L)
{
    L = (struct DNA *)malloc((sizeof(struct DNA)));
    L->next = NULL;
    return L;
}
int Inversionsnum(char *str, int len);
struct DNA *CreatLink(struct DNA *L, int len, int num_m)
{
    struct DNA *P, *S;
    int i,j;
    P = L;
    for(i = 0; i < num_m; i++){
        S = (struct DNA *)malloc(sizeof(struct DNA));
        memset(S->str, '\0', (len+1));
        for(j = 0; j < len; j++)
            scanf("%c", &S->str[j]);
        getchar();
        S->num = Inversionsnum(S->str, len);
        S->next = P->next;
        P->next = S;
        P = P->next;
    }
    return L;
}
int Inversionsnum(char *str, int len)
{
    int s_num,i,j;
    s_num = 0;
    for(i = 0; i < len; i++)
    {
        if(str[i] == 'A'|| str[i] == 'a')
            continue;
        for(j = i+1; str[j] != '\0'; j++){
            if(str[i] > str[j])
                s_num++;
        }
    }
    return s_num;
}
struct DNA *Linksort(struct DNA *L, int num_m)
{
    struct DNA *p, *s, *r, *g, *L1;
    int i;
    L1 = InitLink(L1);
    r = L1;
    for(i = 0; i < num_m; i++){
        p = L->next;
        g = p->next;
        s = L;
        while(g != NULL){
            if((p->num) <= (g->num))
                g = g->next;
            else{
                p = g;
                g = g->next;
            }
        }
        while(s->next != p)
            s = s->next;
        s->next = p->next;
        r->next = p;
        r = p;
    }
    L->next = L1->next;
    return L;
}
int main()
{
    struct DNA *L, *P;
    int str_len, str_num;
    scanf("%d%d", &str_len, &str_num);
    getchar();    
    L = InitLink(L);
    L = CreatLink(L,str_len, str_num);
    L = Linksort(L, str_num);
    for(P = L->next; P!=NULL; P = P->next)
        printf("%s\n", P->str);    
    return 0;
}