Yeah, but that's for a list of three elements. If youI don't understand what you mean. The algorithm only works for sets. If you had the same element in the input twice it would be 'smoked'.
had that list 5000000 times over, just those three
input values, but a much longer list, the disparity
in the range would have less of an impact, and this
algorithm would smoke every other sort in existance.
Yeah, but that's for a list of three elements. If youIt's not really a sort, per se. It's a map. The only part that does anything useful has extremely poor efficiency.
had that list 5000000 times over, just those three
input values, but a much longer list, the disparity
in the range would have less of an impact, and this
algorithm would smoke every other sort in existance.
public static void sort(Integer[] array)
{
int len = array.length;
if(len <= 1)
return;
//sort
int[] differences = new int[len];
int max = 0,
min = 0;
Integer first = array[0];
for(int x = 1, dif; x < len ; x++)
{
differences[x] = dif = compare(first, array[x]);
if(dif > max)
max = dif;
else if(dif < min)
min = dif;
}
max -= min;
int index;
LinkedList[] sparseList = new LinkedList[max+1];
for(int x = 0; x < len ; x++)
{
index = max - (differences[x] - min);
if(sparseList[index] == null)
sparseList[index] = new LinkedList();
sparseList[index].add(array[x]);
}
int count = 0;
for(LinkedList list : sparseList)
if(list != null)
for(Object o : list)
array[count++] = (Integer) o;
}
public static void sort(int[] array)
{
int min = findMin(array);
int max = findMax(array);
System.out.println(min);
System.out.println(max);
int[] map = new int[(max - min) + 1];
for (int i = 0; i < array.length; i++) map[array[i] - min]++;
for (int i = 0, index = 0; i < map.length; i++) {
for (int j = map; j > 0; j--) array[index++] = i + min;
}
}
My code, in its best form to date (mind the Objects,A lot of Objects don't return a scale in their compare to methods. They only return 1, 0, or -1.
I meant it to work for those originally)
max -= min;
<pb>int[] map = new int[(max - min) + 1];
<pb>I know. I was trying to find ways around that (and did, for some). In the end, it wasn't worth it.My code, in its best form to date (mind theObjects,I meant it to work for those originally)A lot of Objects don't return a scale in their
compare to methods. They only return 1, 0, or -1.
Adeodatus:It gets pwnd. Horribly. And if I wanted, I could put in a test for that (casting to longs first) and use Arrays.sort() instead.<pb>max -= min;
What if, max is, say Integer.MAX_VALUE and min is,
say, -1?
</pb>
the disparityIt's a specialized sorting algoritm taking advantage of the value structure. You get the optimum result when you sort all integers in a certain range (they're shuffled). In this special case the algoritm is O(N) where N is the number of integers. This is better than any general sorting algoritm but not that much really (a general sorting algoritm is O(N*logN)). The algoritm degenerates quickly and efforts to generalize it will fail because then it loses it's special structure.
in the range would have less of an impact, and this
algorithm would smoke every other sort in existance.
My code, in its best form to date (mind the Objects,It's a very bad code. For example you're using random accesses in a linked list. That's a no-no! Have you clocked this against an ordinary sort?
I meant it to work for those originally)
For example you're using randomNo you weren't but still, have you clocked your algoritm against an ordinary sort?
accesses in a linked list.
dubwai:It would blow up, right?<pb>int[] map = new int[(max - min) + 1];
Same question.
</pb>
I think this technique would be most useful if youI can be used for sorting. The best performance is when you have a set of shuffled integers from a sequence with just a few missing.
have a large list of sequential numbers where
relatively few are missing and you wan to figure out
which elements are not there.
I can be used for sorting.Obviously.
The best performance isOdd, I could swear I just posted that exact same thing.
when you have a set of shuffled integers from a
sequence with just a few missing.