User talk:Rsathish
Welcome to Wikipedia
[edit]Hope you enjoy contributing to Wikipedia. Be bold in editing pages. Here are some links that you might find useful:
- Try the Tutorial. If you have less time, try Wikipedia:How to edit a page.
- To sign your posts (for eg. on talk pages) use ~~~~ (four tildes). This will insert your name and timestamp. To insert just your name, type ~~~ (3 tildes).
- You can experiment in the Sandbox.
- For help, see Wikipedia:Where to ask a question.
- Some other pages that will help you know more about Wikipedia: Manual of Style and Wikipedia:Five pillars, Wikipedia:Neutral point of view, Wikipedia:Civility, Wikipedia:What Wikipedia is not
- You can contribute in many ways: write a great article, fight vandalism, upload pictures, perform maintainance tasks, contribute to existing projects...
I hope you stick around and keep contributing to Wikipedia. Drop us a note at Wikipedia:New user log.
P.S. Wikipedia is not a place to publish your Original Research.
Best Sort
[edit]It is an innovative o(n) sort with o(n) memory requirements
It is a non-comparison sort which optimizes bin sort at bit level
Best Sort is bin sort with a bin size of 1 bit, where all possible bits are arranged as tree.
The inputs 1,12,1234,12345 will consume 5 bits only.
As 1->2->3->4->5 is the storage structure.
Sorting is similar to bin sort, where a scan of all entries are made, entries are inserted into bins and then bins are read out.
Code listing with documentation:
import java.util.Stack;
/**
* @author R.SATHISH
* email: callbabusats@yahoo.co.in
* Characteristics:
* Insert = o(bits in a key) = o(l) for a given key , but much less processing = o(ln)
* Print = o(bits in a key) and recursive printing = o(ln)
* Memory = every bit stores pointers to its children = o(n(rp+1)l), rp+1 is constant = o(constant*nl)
* = o(ln) = Memory consumption is proportional to 'n' and 'l'
*
* Data Structure description:
* The data structure applies universe restricted sort as "Every bit in the key points to all possible next bits."
* Hence BestTree3 is a highly optimal strategy of universe restricted sort.
* 1234
* 1235
* is stored as
* 1->2->3->4
* 3->5
*
* Memory required is o(bits), but every bit requires o(radix) references.
* Hence total memory per key is o(lr) ~ o(l)
* Memory required is dependent on radix,length and number of elements.
*
* To store a 10digit 4-byte unicode string, per bit 2^32 sized array is required. (=640 refernces per key).
* To store same key in binary requires
* -conversion to binary string of 32*10 = 320 digits and 2 references per digit. (=640 refernces per key).
*
* While insertion and printing are dependent on the number of digits linearly.
* Hence it is advisable to perform the sort with maximum radix.
*
* Applications could parallely convert from one radix to another in first thread,
* and feed the data to BestSort in second Thread. Similarly when second thread prints the sorted keys
* first thread could convert to desired radix.
*
* This strategy will work very efficiently in 2-CPU machine.
* As, to insert/print binary key requires 320 operations, while to insert/print unicode requires 10 operations.
* Applications:
* All sorts with adequate memory availability.
* Performs well in PCs. Gives o(1) outputs while consuming tens of MB.
* Ideal for sorting decimals.
*
* Innovative breakthrough sorting algorithm which offers
* 1.o(ln) insertion o(t) in variable width keys
* 2.o(n) memory consumption. o(t) in variable width keys
* 3.o(ln) printing o(t) in variable width keys
* 4.Handles keys in any radix.
* 5.Handles keys of any length (keys need not be constant width)
*
* Prior Art
* None
*
* @throws java.lang.OutOfMemoryError
*/
public class BestTree3 implements BestTree{
class RadixBit {
RadixBit children[] = null;
boolean hasChild = false;
RadixBit() {
super();
children = new RadixBit[radix];
}
RadixBit at(int at) {
return (RadixBit) children[at];
}
boolean get(int at) {
return children[at] != null;
}
public boolean isHasChild() {
return hasChild;
}
RadixBit set(int at) {
if (get(at)) {
return at(at);
}
hasChild = true;
RadixBit child = new RadixBit();
children[at] = child;
return child;
}
public void setHasChild(boolean hasChild) {
this.hasChild = hasChild;
}
}
int keyL;
int radix;
RadixBit root = null;
BestTree3(int radix, int keyL) {
this.radix = radix;
this.keyL = keyL;
root = new RadixBit();
}
public void insert(int[] key) {
RadixBit last = root;
for (int i = 0; i < key.length; i++) {
last = last.set(key[i]); // Every bit is set once. Hence o(1).
//Please note the difrence from bin sort, where sorting is done 'k'
// times...
//Here insertion is done once per bit per key..i.e we write to a
// magic box once
//and read from the magic box to see sorted results in o(n).
}
}
public void print() {
print(root, "");
}
//Stack stack = new Stack();
private void print(RadixBit last, String prefix) {
int i = 0;
for (; i < radix; i++) {
if (last.get(i)) {
print(last.at(i), prefix + "." + i); // Every key is printed
// once. Hence o(1);
}
}
if (last.isHasChild() == false) {
//System.out.println(prefix);
}
}
}
/**
* @author R.SATHISH
* email:callbabusats@yahoo.co.in
*
* Insert = o(n),o(in),o(rn)
* Print = o(n),o(in),o(rn)
* Memory = o(r^(l+1)),o(r^l),o(nl)
*
*/
public interface BestTree {
/*
* print writes the keys in sorted order to standard output.
* Few versions write per bit while others per key.
*/
public void print();
/*
* insert reads and includes the key to the data store.
* Few versions of insert convert the key to an intermediate radix.
* Few versions compute the value of the key from its digit and work at key level.
* @param key Digits of key with MSB in 0 in the required radix.
*/
public void insert(int key[]);
}
/**
* @author R.SATHISH
* email:callbabusats@yahoo.co.in
*
* Symbols:
* 'n' - Number of keys to be sorted
* 'r' - radix of keys digits
* 'l' - width of a key (assumes constant width zero padded keys)
* 'p' - Pointer size
* 'i' - internal radix
* 'c' = ln-i(r)
* 't' = Number of digits in all keys = ln in constant width keys
*
* This Java class demonstrates O(ln) capabilitis of best sort. This class is the
* core patentable sorting algorithm.
*
* Step 1 - Creates a data store for the keys
* Step 2 - Accepts keys and inserts into the data store
* Step 3 - Prints out the sorted keys
*
* This is Version 1 of Best Sort.
*
* Prior art:
* Best Sort is an innovation without precdence.
* It comes under distribution sort, universe restricted sort.
*
* Best sort is a <b>single pass</b> sort.All best sorts sort the data only once.
*
* But few versions, sort per bit, while few per key.
* Few versions require exponential memory, while others linear memory.
*
* <b> The simulations show that Javas quick sort outperform Best Sort.
* (This version of Best Sort is not the most optimal implementation).
* But Best Sort provides o(ln) sorting while quick sort o(nlogn).
* Best sort outperforms quick sort when number of keys are exponentially greater than number of digits.
* </b>
*
*
*/
import java.util.*;
public class BestSort {
public static void main(String[] args) {
/*
* Command line parsing section.
*/
if (args.length != 3) {
System.out.println("Usage:java BestSort radix keyLength count");
return;
}
/*
* Initalisation section
*/
int radix = Integer.parseInt(args[0]);
int l = Integer.parseInt(args[1]);
int count = Integer.parseInt(args[2]);
/*
* Creates the Best Tree Data Structure which supports Best Sort.
*/
BestTree tree1 = new BestTree32(radix, l);
// BestTree tree2 = new BestTree3(radix, l);
// BestTree tree3 = new BestTree3(radix, l);
int arr[] = new int[l];
long ins1,ins2,ins3,st,ins0;
ins1=ins2=ins3=0;
String conv[] = new String[count];
/*
* Insertion section.
*/
for (; count > 0; count--) {
StringBuffer str = new StringBuffer(l);
for (int k = 0; k < l; k++) {
arr[k] = (int) (Math.random() * radix); // Randomly generates key digits
str.append('0'+arr[k]);
}
conv[conv.length-count] = str.toString();
st = System.currentTimeMillis();
tree1.insert(arr);// o(l) insertion
ins1 += System.currentTimeMillis() -st;
// st = System.currentTimeMillis();
// tree2.insert(arr);// o(l) insertion
// ins2 += System.currentTimeMillis() -st;
//
// st = System.currentTimeMillis();
// tree3.insert(arr);// o(l) insertion
// ins3 += System.currentTimeMillis() -st;
}
/*
* Sorted output printing section.
*/
System.out.println("Java Arrays.sort......");
st = System.currentTimeMillis();
Arrays.sort(conv);
st = System.currentTimeMillis() - st;
System.out.println("executed in "+(st)+" ms");
System.out.println("BestSort1......");
st = System.currentTimeMillis();
tree1.print();//o(n) printing
st = System.currentTimeMillis() - st;
System.out.println("executed in "+(st+ins1)+" ms");
System.out.println("Inserted in "+(ins1)+" ms");
System.out.println("Printed in "+(st)+" ms");
// System.out.println("BestSort2......");
// st = System.currentTimeMillis();
// tree2.print();//o(n) printing
// st = System.currentTimeMillis() - st;
// System.out.println("executed in "+(st+ins2)+" ms");
// System.out.println("Inserted in "+(ins2)+" ms");
// System.out.println("Printed in "+(st)+" ms");
//
// System.out.println("BestSort3......");
// st = System.currentTimeMillis();
// tree3.print();//o(ln) printing
// st = System.currentTimeMillis() - st;
// System.out.println("executed in "+(st+ins3)+" ms");
// System.out.println("Inserted in "+(ins3)+" ms");
// System.out.println("Printed in "+(st)+" ms");
}
}
Nomination of Private class data pattern for deletion
[edit]
The article will be discussed at Wikipedia:Articles for deletion/Private class data pattern until a consensus is reached, and anyone, including you, is welcome to contribute to the discussion. The nomination will explain the policies and guidelines which are of concern. The discussion focuses on high-quality evidence and our policies and guidelines.
Users may edit the article during the discussion, including to improve the article to address concerns raised in the discussion. However, do not remove the article-for-deletion notice from the top of the article.