CODEWITHSUNDEEP
c++
user1436187
user1436187

Reputation: 3376

sorting vector<vector<bool>> based on the content of vector<bool>

I have 2000 vector<vector<bool>> and each vector<bool> contains 200 elements , I am going to sort this vector of vectors. Supposing that the elements in vector<bool> are a one binary number.

original data:

vector 1: 1,1,1
vector 2: 1,0,1
vector 3: 0,0,0
vector 4: 1,0,0

After sorting:

vector 3: 0,0,0
vector 4: 1,0,0
vector 2: 1,0,1
vector 1: 1,1,1

It is possible to use sort with a special predicate but surprisingly when I call sort without a predicate it seems to work anyway. 

    vector<bool> A = {1, 1, 1};
    vector<bool> B = {1, 0, 1};
    vector<bool> C = {0, 0, 0};
    vector<bool> D = {1, 0, 0};

    vector < vector<bool> > v = {A,B,C,D};

    sort(v.begin(),v.end());

and the order is as "after sorting" above.

Why does it work without a special predicate?

Upvotes: 0

Views: 1153

Answers (3)

notadam
notadam

Reputation: 2884

Use a simple bubble sorting algorithm on the elements of the outer vector (which are vectors as well), and the condition of swapping would be this:

for (int i=0; i<200; i++)
    if (vec1[i] > vec2[i]) vec1.swap(vec2);
    /* vec1 and vec2 are the two vectors you
    compare when bubble sorting the outer vector */

Because if you take two binary numbers, iterate through them, and compare each corresponding digit, then the greater of the two numbers is the one that has the highest digit that's a one and the corresponding digit in the other number is a 0. Like this:

0011010110101010000111011011

0010101011101000011101101010

Without converting them to decimal, it's easy to tell that the top one is larger. The first three digits are the same, but the fourth one is greater in the top number. The rest don't matter, this makes the top number bigger. Therefore, it's simple to use this as a swapping condition in bubble sorting.

Upvotes: 0

Vlad from Moscow
Vlad from Moscow

Reputation: 311058

It is enough simply to apply standard algorithm std::sort declared in header <algorithm> because there is defined operator < for vectors provided that all boolean vectors have the same size.

Here is an example

#include <iostream>
#include <vector>
#include <algorithm>

int main() 
{
    std::vector<std::vector<bool>> v =
    {
        { 1, 1, 1 }, { 1, 0, 1 }, {0, 0, 0 }, { 1, 0, 0 }
    };

    std::sort( v.begin(), v.end() );

    for ( const std::vector<bool> &v1 : v )
    {
        for ( bool b : v1 ) std::cout << b << ' ';
        std::cout << std::endl;
    }

    return 0;
}

The output is

0 0 0 
1 0 0 
1 0 1 
1 1 1

Otherwise you could use algorithm std::accumulate in a predicate of std::sort

Upvotes: 5

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

std::sort can take a Compare function. So just define a compare function on std::vector<bool> doing what you expect.

Hence you need to define a convention about how to compare two std::vector<bool> of different lengths.

BTW, it looks like you are re-inventing bignums, why don't you use some existing library like gmplib?

Upvotes: 3

Related Questions