Best algorithm to sort semi-sorted arrays?
I am trying my hand at the hutter prize (http://prize.hutter1.net/)
My current compression algorithm sorts an array of Comparable Objects every main cycle.
-This array of objects can potentically increase by one object per cycle.
-Each object's comparision value can change per cycle, however its order is mostly kept.
This means that the over all order of the objects are similar between cycles.
Is there an sorting algorithm which can take advantage of the semi-sorted state of the array?
I was using the default Arrays.sort() however it does not seem to make much use of the semi-sorted input array and is too slow for my use.
In order to speed up the sorting i have relaxed the need to be in strict order. I.e there can be some objects out of order.
To this end I have developed a BucketSort which i thought should speed up the sorting however it seems to have the opposite effect!
Is there any reason why this implementation is quite slow? (three times as slow as Array.sort() )
privatestaticint MAX_BUCKET=65535;
privatestatic Word[] buckets=new Word[MAX_BUCKET];
publicstaticvoid bucketSortReverse (Word[] a,int n)
{
int i;
int count=1;
int index;
Word curr;
// fill up the buckets with the input words
for (i=0;i<n;i++)
{
curr=a[i];
index=(int) (curr.probablility*MAX_BUCKET);
curr.next=buckets[index];
buckets[index]=curr;
}
// iterate over the buckets and construct the sorted words
for (i=0;i<MAX_BUCKET;i++)
{
curr=buckets[i];
if (curr!=null)
{
while (curr!=null)
{
a[n-count++]=curr;
curr=curr.next;
}
buckets[i]=null;
}
}
}
*NOTE* Currently my input Word array contains a maximum of 6000 words.
Lowering the number of bins reduces the accuraccy of the sort and does not provide much increase in speed :(
I have found some Open Source code which by default performs very similarly to Arrays.sort in terms of speed and have modified it to be non-strict in its ordering.
This modified sorting algothim is approximately 15% faster but is still really not fast enough.
By reducing the strict ordering of the sorting algorithm i have also reduced the level of compression. Ultimately i would like to have a fast sorting algothrim which takes into acount semi-sorted objects with out reducing strictness of the sort.
Any ideas?>
