As I mentioned before, (assuming there is no 'secondary' key), what makes
this sorting problem unusual is the very small number of distinct key values
(just 32). I am certain that the most efficient sort will take advantage of
that.

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

----- Original Message -----
From: Craig Lee <picme@ENLIGHT.CA>
To: <PICLIST@MITVMA.MIT.EDU>
Sent: Wednesday, August 23, 2000 7:30 PM
Subject: Re: [OT] FAST C/C++ sorting


> Could you better explain what you are trying to do.  Would the number
> 00001111 come before 00011110, or when there is the same number of ones
> is there a secondary sort to bring the binary implementation into play?
>
> i=0;
> j=0;
> mask=1;
>
> for(i=0;i<32;i++)
> {
>         if(mask & value) j++;
>         mask <<= 1;
> }
>
> Using the j parameter to determine the exchange in a quicksort.
> I'm sure there are faster implementations shifting into the carry.
>
> As far as what's the quickest method, radix will behave similarily
> to quicksort with large random files.  Merge behaves similarily to
> radix for random data.  I remember an old program that came with
> Turbo C that evaluated which method would be quicker based on the
> input data.  Perhaps you could test your data with it.
>
> Craig
>
>
> > -----Original Message-----
> > From: pic microcontroller discussion list
> > [mailto:PICLIST@MITVMA.MIT.EDU]On Behalf Of Samuel Winchenbach
> > Sent: Wednesday, August 23, 2000 3:46 PM
> > To: PICLIST@MITVMA.MIT.EDU
> > Subject: [OT] FAST C/C++ sorting
> >
> >
> > Hello all.
> > I have about 8 million 32 bit integers that I need to sort (by the
number
> > of ones in the binary representation of the integer) I am wondering what
> > the fastest sort is? Merge? Quicksort? Fast Quicksort? Radix?
> > I am storing my values in my data structure contained within a vector.
So
> > I know I will need to manipulate the sort function around a bit. I have
> > already overridden all the needed operators. If anyone can give me
> > suggestions I would appreciate it.
> > Writing a Quine-McCluskey program is more difficult that I would have
> > ever thought.
> >
> > --
> > http://www.piclist.com hint: The list server can filter out subtopics
> > (like ads or off topics) for you. See http://www.piclist.com/#topics
> >
> >
> >
>
> --
> http://www.piclist.com hint: The list server can filter out subtopics
> (like ads or off topics) for you. See http://www.piclist.com/#topics
>
>

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.