This discussion is archived
1 2 3 42 Replies Latest reply: Dec 20, 2004 1:49 PM by 800323 Go to original post
• ###### 15. Re: HashSort?
Currently Being Moderated
Yeah, but that's for a list of three elements. If you
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.
I 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'.
• ###### 16. Re: HashSort?
Currently Being Moderated
Yeah, but that's for a list of three elements. If you
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.
It's not really a sort, per se. It's a map. The only part that does anything useful has extremely poor efficiency.
• ###### 17. Re: HashSort?
Currently Being Moderated
The algorithm could be modified to jut increment the associated array element as it came across each value. And the empty element elmination can be fixed by creating a new array and just iterating over the map putting each index in the array for the values it finds in them (e.g. if there is a 3 in element 10, put three tens in the array. This algorithm should be fast for large 'full' (few gaps) numeric data. Basically, in it's best case it's O(n). In it's worst case it's O(inifinity). I don't know what else to call it. It has an unbounded downside.
• ###### 18. Re: HashSort?
Currently Being Moderated
My code, in its best form to date (mind the Objects, I meant it to work for those originally)
``````      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;
for(int x = 0; x < len ; x++)
{
index = max - (differences[x] - min);
if(sparseList[index] == null)
sparseList[index] = new LinkedList();
}

int count = 0;
for(LinkedList list : sparseList)
if(list != null)
for(Object o : list)
array[count++] = (Integer) o;
}``````
• ###### 19. Re: HashSort?
Currently Being Moderated
why not just:
``````    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;
}
}
``````
• ###### 20. Re: HashSort?
Currently Being Moderated
My code, in its best form to date (mind the Objects,
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.
• ###### 21. Re: HashSort?
Currently Being Moderated
``max -= min;``
<pb>
What if, max is, say Integer.MAX_VALUE and min is, say, -1?
</pb>

dubwai:
``int[] map = new int[(max - min) + 1];``
<pb>
Same question.
</pb>
• ###### 22. Re: HashSort?
Currently Being Moderated
My code, in its best form to date (mind the
Objects,
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.
I know. I was trying to find ways around that (and did, for some). In the end, it wasn't worth it.

``max -= min;``
<pb>
What if, max is, say Integer.MAX_VALUE and min is,
say, -1?
</pb>
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.
• ###### 23. Re: HashSort?
Currently Being Moderated
the disparity
in the range would have less of an impact, and this
algorithm would smoke every other sort in existance.
It'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.

I would use it under very controlled conditions only. It's a better mousetrap okay but it will catch a very rare mouse only. -:) The built-in sorting algoritm in Java is very hard to beat.
• ###### 24. Re: HashSort?
Currently Being Moderated
My code, in its best form to date (mind the Objects,
I meant it to work for those originally)
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?
• ###### 25. Re: HashSort?
Currently Being Moderated
For example you're using random
accesses in a linked list.
No you weren't but still, have you clocked your algoritm against an ordinary sort?

Just because you use int wrapper objects doesn't mean the algoritm has become general and will work with objects of any class.
• ###### 26. Re: HashSort?
Currently Being Moderated
dubwai:
``int[] map = new int[(max - min) + 1];``
<pb>
Same question.
</pb>
It would blow up, right?

If you look at my other posts I note that while this algorithm has a best case of O(n) it's worst case is unbounded. I'm not arguing that it's great way to do things and there are a bunch of improvements that can be made to my code.

AlI was saying is that I don't understand why Adeodatus' code is so complicated.
• ###### 27. Re: HashSort?
Currently Being Moderated
I think this technique would be most useful if you have a large list of sequential numbers where relatively few are missing and you wan to figure out which elements are not there.
• ###### 28. Re: HashSort?
Currently Being Moderated
I think this technique would be most useful if you
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. The best performance is when you have a set of shuffled integers from a sequence with just a few missing.
• ###### 29. Re: HashSort?
Currently Being Moderated
I can be used for sorting.
Obviously.
The best performance is
when you have a set of shuffled integers from a
sequence with just a few missing.
Odd, I could swear I just posted that exact same thing.
1 2 3