Okay, this is just off the top of my head. This is just the basic idea.
You'll have to properly handle the edge conditions.

Also: There are many tricks for counting the one bits in a word, many of
them much faster than the brute force technique. Even the fastest of these
is a bit slow, so you might be better off making  a prepass to compute and
store the key value in each element.

The basic subfunction will take as an argument a subvector of the data, and
will partition that data into two halves, based on the high bit of the key,
something like this:

first = 0;
last = n-1;

INVARIANT: all items from 0 through (first-1) have the high bit clear
                      all items from (last+1) through n-1 have the high bit
set

while (first < last)
{
    while ( 0 == key(first) & 0x20 )
       ++first;

    while (0 != key(last) & 0x20 )
       --last;

    // At this point: key(first) has hi bit set, key(last) has hi bit clear,
so...

    swap element[first] and element[last];
    ++first;
    --last;
}

Now you have partitioned by the high bit. Now do the same thing
(recursively), based on the second bit, to each of the two halves of your
array. This will give you four pieces, recurse into them exchanging on the
third bit giving eight pieces, recurse again swaping on the fourth bit,
given 16 pieces, one final pass swapping on the fifth (least significant)
bit will put everything in order.

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



----- Original Message -----
From: Samuel Winchenbach <swinchen@EECE.MAINE.EDU>
To: <PICLIST@MITVMA.MIT.EDU>
Sent: Wednesday, August 23, 2000 8:06 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?
>
> *SNIP*
>
> Thanks for the response.
>
> 0000
> 0001
> 0010
> 0011
> 0100
> 0101
> 0110
> 0111
> 1000
> 1001
> 1010
> 1011
> 1100
> 1101
> 1110
> 1111
>
> would be sorted to:
>
> 0000
>
> 0001
> 0010
> 0100
> 1000
>
> 0011
> 0101
> 0110
> 1001
> 1010
> 1100
>
> 0111
> 1011
> 1101
> 1110
>
> 1111
>
>
> As you can see the numbers are sorted by the number of one's in the binary
> representation.  The actual value has nothing to do with it.  So what I
> have done is the following:
>
>
> class quine
> {
>   private:
>
>   public:
>     int value;
>     int blanks;
>
>     bool operator > (quine &rightside) const;
>     bool operator >= (quine &rightside) const;
>     bool operator < (quine &rightside) const;
>     bool operator <= (quine &rightside) const;
>     bool operator == (quine &rightside) const;
> };
>
> value is the actual number (NOT the number of ones in the binary
> representaion)
>
> next I store all 8 million numbers in a vector of quine:
>
> vector<quine> mterms;  file://minterms
>
> for( blah blah.. )
> {
>   file://cycle throught the text file, and push a type "quine" into the
vector
>   file://after setting its value.
> }
>
> now the next thing I want to do is sort my vector of type quine.  not by
> value, but by the number of one's in the binary representation of value.
>
> I already have this working using selection sort.... but by god, I think I
> would grow old and die before it finished.  Radix or Quicksort seem the
> best bet... but I have no idea how to implment them... and nothing from
> the STL will help me either (I guess sort in <algorithm> is quicksort..
> but I do not believe it will work due to my strange data stucture.
>
> Thanks again,
>
> Sam
>
> --
> 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.