1 2 3 Previous Next 42 Replies Latest reply: Dec 20, 2004 3:49 PM by 800323 Go to original post RSS
      • 30. Re: HashSort?
        807596
        Odd, I could swear I just posted that exact same
        thing.
        You mean where you repeat what I posted in #23?
        • 31. Re: HashSort?
          807596
          You mean where you repeat what I posted in #23?
          Where?
          • 32. Re: HashSort?
            807596
            You mean where you repeat what I posted in #23?
            Where?
            Everywhere! You've been repeating everything I just stated in this whole thread. I don't know if you didn't understand my replies or if you choose to ignore them but it became quite surrelaistic when you eventually noticed one of my replies and decided that I had been repeating you -:)

            Check for example your post 12 where you proudly presents what I just said in 9 and 11.
            • 33. Re: HashSort?
              807596
              You mean where you repeat what I posted in #23?
              Where?
              Everywhere! You've been repeating everything I just
              stated in this whole thread.
              No. I haven't.
              I don't know if you
              didn't understand my replies or if you choose to
              ignore them
              I usually ignore your posts.
              but it became quite surrelaistic when you
              eventually noticed one of my replies and decided that
              I had been repeating you -:)
              You responded to me telling me what I wrote in the post you were repsponding to.
              Check for example your post 12 where you proudly
              presents what I just said in 9 and 11.
              I hadn't read what you wrote and I wasn't replying to you.
              • 34. Re: HashSort?
                807596
                The best performance is
                when you have a set of shuffled integers from a
                sequence with just a few missing.
                While we are at it. What difference does shuffling the integers have on the performance?
                • 35. Re: HashSort?
                  796440
                  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.
                  I know. I just wanted to point that out for the OP's benefit. That kind of thing is a fairly common and subtle gotcha, IME.
                  • 36. Re: HashSort?
                    807596
                    I know. I just wanted to point that out for the OP's
                    benefit. That kind of thing is a fairly common and
                    subtle gotcha, IME.
                    You could make an array of arrays in order to support the ful range of long (or an unbounded range (arrays of arrays of arays etc.) but clearly, if your range is that large you should not be using this algorithm unless you have a specific type of data.

                    I suppose this is a good technique to know if you ever run into a problem where it fits.
                    • 37. Re: HashSort?
                      807596
                      No. I haven't.

                      I usually ignore your posts.

                      You responded to me telling me what I wrote in the
                      post you were repsponding to.

                      I hadn't read what you wrote and I wasn't replying to
                      you.
                      So now that you've made 10,000 posts you've become so important that people must request an audience to be allowed to discuss with you? Am I supposed to feel sorry now that the Great Dubwai won't share his deep insights with me? Thanks for the laugth of the evening.
                      • 38. Re: HashSort?
                        807596
                        So now that you've made 10,000 posts
                        Have I? Cool.
                        you've become so
                        important that people must request an audience to be
                        allowed to discuss with you?
                        No. I've had more than enough discussions with you.
                        Am I supposed to feel
                        sorry now that the Great Dubwai
                        won't share his deep
                        insights with me?
                        No, my intention is not to make you feel anything. I just stated the truth I tend to skip your posts. It hasn't been worth it in the past.
                        Thanks for the laugth of the
                        evening.
                        Whatever floats your boat. All I'm saying is that it's weird to reply to someone and repeat back to that person what he wrote as if it was a correction. More than one person replies with the same basic info all the time here. It's not the same as replying to a post to echo it back as if it were new info.
                        • 39. Re: HashSort?
                          800323
                          Way back when (must be getting old) we called this a Bucket Sort (or some form of it). A Google search on "bucket sort" still turns up alot of discussion on the topic.
                          • 40. 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?
                            I haven't clocked it against a different sort, but I did run a rather extensive benchmarking a while ago, tracking its average time for sorting for lists from length 10000 to 1000000, each list containing "Random" Integers (since I was using util.Random, some of the larger lists would have exceeded its period, but that shouldn't have had much of an effect) in the range [0, 100). After graphing the progression, I found it to be linear (as expected).

                            Just because you use int wrapper objects doesn't mean
                            the algoritm has become general and will work with
                            objects of any class.
                            Go figure. At home I use Comparable and then test for sortable types, range, etc. I decided not to post the full code because I don't like most of it. It was written by a past me who apparently had fairly poor syntax (like all our past selves).
                            • 41. Re: HashSort?
                              807596
                              Sorry to resurrect such an old topic, but I have been absent from the forums for a while. Thanks for all of your suggestions, I am trying to implement them.

                              One more question however:

                              Should I run through the array of numbers, compute the mean, than eliminate numbers too far away from the mean to improve memory usage. For example:
                              myArray is array of unsorted numbers
                              calc avg
                              int[] extremes = new int[some value];
                              int j =0;
                              for(int k=0;k<myArray.length;k++)
                              if(myArray[k]-avg>100000||myArray[k]-avg<-100000)
                              extremes[j++] = myArray[k];

                              later on I would have to add the extremes back into the finished array...
                              This would eliminate the extreme values and have significant memory savings. Do you think this memory savings is worth the extra loops?

                              Yes, I do know about the Comparable interface, but I couldn't figure out an efficient implementation with this sort using it.
                              Thanks everyone for helping me out.
                              • 42. Re: HashSort?
                                807596
                                Yes, I do know about the Comparable interface,
                                but I couldn't figure out an efficient
                                implementation with this sort using it.
                                Don't feel bad, there isn't one.

                                Should I run through the array
                                of numbers, compute the mean,
                                than eliminate numbers too far
                                away from the mean to improve
                                memory usage.
                                Maybe. If you can keep it order N. Too much of this kind of thing makes for a merg-ish sort, and at that point you should just switch to a radix sort.
                                1 2 3 Previous Next