Q612: DNA Sorting

// Run time: 0.110
#include <stdio.h>
typedef struct {
    char str[51];
    int cnt;
    int sort;
} string;
string DNA[100];

int calculate(char *str, int len);
void print(string *s, int n);

int main()
{
    int num;
    int len, n;
    int i, j;
    scanf("%d", &num);
    while (num--)
    {
        scanf("%d%d\n", &len, &n);

        // DNA string input
        for ( i = 0; i < n; i++)
        {
            gets(DNA[i].str);
            DNA[i].sort = i;
        }
        // calculate the length of each DNA's string
        for ( i = 0; i < n; i++)
            DNA[i].cnt = calculate(DNA[i].str, len);

        if (n != 1)
           print(DNA, n);

        // if only one input
        else
           printf("%s\n", DNA[0].str);

        if (num)
            printf("\n");
    }

    return 0;
}

int calculate(char *str, int len)
{
    int i, j;
    int cnt = 0;
    for ( i = 0; i < len-1; i++)
        for ( j = i+1; j < len; j++)
            if (str[i] > str[j])
                cnt++;

    return cnt;
}

void print(string *s, int n)
{
    int i, j;
    int index;
    int count = 0;
    int min;
    bool state[n];

    for ( i = 0; i < n; i++)
        state[i] = true;

    for (;;)
    {
        for ( i = 0; i < n; i++)
            if (state[i])
                break;

        min = s[i].cnt;
        index = i;
        state[i] = false;

        for ( j = 0; j < n; j++)
        {
            if (min > s[j].cnt && state[j])
            {
                // 如果發現更小的，要把之前的 state 還原成true
                state[index] = true;
                min = s[j].cnt;
                state[j] = false;
                index = j;
            }
        }

        printf("%s\n", s[index].str);

        if (++count == n)
            return;
    }
}