This discussion is archived
1 2 3 Previous Next 42 Replies Latest reply: Dec 20, 2004 1:49 PM by 800323 Go to original post RSS
  • 15. Re: HashSort?
    807596 Newbie
    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?
    807596 Newbie
    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?
    807596 Newbie
    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?
    807596 Newbie
    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;
             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 Newbie
    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?
    807596 Newbie
    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?
    796440 Guru
    Currently Being Moderated
    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 Newbie
    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.


    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 Newbie
    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?
    807596 Newbie
    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?
    807596 Newbie
    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?
    807596 Newbie
    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?
    807596 Newbie
    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?
    807596 Newbie
    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?
    807596 Newbie
    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.