BestSort.java Listing
/**
* @author R.SATHISH
*
* This Java class demonstrates O(n) capabilitis of best sort.
* This class is the core patentable sorting algorithm.
*
* This is Version 1 of Best Sort.
*/
public class BestSort {
public static void main(String[] args) {
if (args.length != 2) {
System.out.println("Usage:java BestSort radix keyLength");
return;
}
int radix = Integer.parseInt(args[0]);
int l = Integer.parseInt(args[1]);
BestTree tree = new BestTree(radix, l);
int arr[] = new int[l];
int min = (int) Math.pow(radix, l - 1);
int max = min * radix;
for (int i = min; i < max; i++) {
int j = i;
j = (int) (Math.random() * i);
int div = min;
for (int k = 0; k < l; k++) {
arr[k] = j / div;
arr[k] %= radix;
div /= radix;
}
tree.insert(arr);
}
tree.print();
}
}
/*
SAMPLE OUTPUT FOR RADIX - 10, KEY LENGTH - 2
0.0.
0.1.
0.2.
0.3.
0.4.
0.6.
0.8.
0.9.
1.0.
1.1.
1.2.
1.3.
1.5.
1.6.
1.7.
1.8.
1.9.
2.0.
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
2.8.
2.9.
3.0.
3.2.
3.4.
3.5.
3.6.
3.7.
4.0.
4.2.
4.7.
4.9.
5.1.
5.4.
5.9.
6.2.
6.4.
6.7.
7.1.
7.2.
7.3.
9.3.
*/
/**
* @author R.SATHISH
*
* This is the core patentable data structure - Best Tree.
* This is Version 1 of Best Tree.
*/
import java.util.BitSet;
public class BestTree {
BitSet tree;
int radix;
int keyL;
BestTree(int radix, int keyL) {
this.radix = radix;
this.keyL = keyL;
tree = new BitSet((int) Math.pow(radix, keyL + 1));
}
public void insert(int[] key) {
int last = 0;
for (int i = 0; i < key.length; i++) {
last = last * radix + key[i] + 1;
int pos = last;
tree.set(pos - 1); // Every bit is written once. Hence o(1).
}
}
public void print() {
int max = (int) Math.pow(radix, keyL + 1);
int i = (max / radix - 1) / (radix - 1) - 1;
int j = i;
for (; i < max; i++) {
if (tree.get(i)) {
int k = i - j;
int div = max / (radix * radix);
String out = "";
while (div > 0) {
int t = ((int) (k / div)) % radix;
out += t + ".";
div /= radix;
}
System.out.println(out); // Every key is printed once. Hence o(1);
}
}
}
}