UVa 612 - DNA Sorting

/*
 * @author Divyanshu
 * @mail divyanshu17x@gmail.com
 * @place GNDU RC SATHIALA
 * @judge uva.onlinejudge.org
 * @verdict Accepted 
 * @problem UVa-612 -DNA SORTING
 * @problemType  stable_sort based on inversion index count

 */


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

class Main {
public static void main(String args[]) throws IOException {

class NodeTree implements Comparable<NodeTree> {
//inversion index is total swap required to swap an array in order
int inversionIndex = 0, position;
char array[];

public NodeTree(int pos, char array[]) {
this.position = pos;
this.array = array;
//calculate the inverion index as per the problem spec of comparing DNA CODE character
for(int i = 0 , length = array.length; i < length; ++i )
{
for(int j = i+1 ; j<length ; ++j)
{
// if the character compared are out of order , increment the inversion index
if(array[j] < array[i] )++inversionIndex;
}
}
}

/*
* do the natural ordering of the nodes in tree as per specs . the
* natural odering will be feeded to TreeSet for inorder ascending
* order sorting with log(n) commplexity basically we just gotta find
* out the order( to place a node earlier or later)of a node with
* respect to other node as per specs rest the tree set will
* automate the sorting order for each node added.
* finally a stable sort is accomplished
*/
@Override
public int compareTo(NodeTree o) {
if (this.inversionIndex != o.inversionIndex) {
return this.inversionIndex - o.inversionIndex;
}
return this.position - o.position;
}

}
// initialise reader
Reader.init(System.in);
int cases = Reader.nextInt();

//usin a string buffer for showing DNA sorted code strings in a file
StringBuffer sb = new StringBuffer();
while (cases-- > 0) {
// input length and total DNA code strings
int length = Reader.nextInt(), ttlCodes = Reader.nextInt();

TreeSet<NodeTree> set = new TreeSet<>();
int pos;

// input DNA code strings
// and add each string as a NodeTree object to a TreeSet
for ( pos = 0; pos++ < ttlCodes ;) {

set.add(new NodeTree(pos, Reader.reader.readLine().trim()
.toCharArray()));
}
//print the DNA data set as required
for(NodeTree n : set )
{
//new String object Allocates a new String so that it represents 
//the sequence of characters currently contained in the character array argument.
sb.append(new String(n.array)+"\n");
}

if(cases > 0) sb.append("\n");

}
System.out.print(new String(sb));

}

}

/** Class for buffered reading int and double values */

class Reader {
static BufferedReader reader;
static StringTokenizer tokenizer;

/** call this method to initialize reader for InputStream */
static void init(InputStream input) {
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}

/** get next word */
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}

static int nextInt() throws IOException {
return Integer.parseInt(next());
}

}