[UVA][sort] 612 - DNA Sorting
DNA Sorting
| DNA Sorting |
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 of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets.The first line of each dataset contains two integers: a positive integer n (
)
giving the length of the
strings; and a positive integer m (
)
giving the number
of strings. These are followed
by m lines, each containing a string of length n.
Output
For each dataset, output the list of input strings, arranged from ``most sorted'' to ``least sorted''. If two or more strings are equally sorted, list them in the same order they are in the input file.Print a blank line between consecutive test cases.
Sample Input
1 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT
Sample Output
CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA
根據DNA未排序程度做排序, 相同則依輸入順序
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int in, v;
} Order;
int cmp(const void *i, const void *j) {
Order *a, *b;
a = (Order *)i, b = (Order *)j;
if(a->v != b->v)
return a->v - b->v;
return a->in - b->in;
}
int main() {
int t, n, m, i, j, k;
char dna[101][101];
scanf("%d", &t);
while(t--) {
scanf("%d %d", &m, &n);
Order D[101];
for(i = 0; i < n; i++) {
scanf("%s", dna[i]);
int sum = 0;
for(j = 0; j < m; j++) {
for(k = j+1; k < m; k++) {
if(dna[i][j] > dna[i][k]) {
sum++;
}
}
}
D[i].v = sum, D[i].in = i;
}
qsort(D, n, sizeof(Order), cmp);
for(i = 0; i < n; i++) {
puts(dna[D[i].in]);
}
if(t)
puts("");
}
return 0;
}