1 2 3 Previous Next 42 Replies Latest reply: Dec 20, 2004 3:49 PM by 800323 Go to original post RSS
      • 15. Re: HashSort?
        807596
        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?
          807596
          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?
            807596
            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?
              807596
              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;
                       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;
                    }
              • 19. Re: HashSort?
                807596
                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?
                  807596
                  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?
                    796440
                    Adeodatus:
                    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?
                      807596
                      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.


                      Adeodatus:
                      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?
                        807596
                        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?
                          807596
                          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?
                            807596
                            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?
                              807596
                              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?
                                807596
                                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?
                                  807596
                                  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?
                                    807596
                                    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.