C++

Forum

 
Finding a way to count the number of comparison in C++ STL sort

Song Tung (18)
Hi everyone,

I'm trying to find a way to count the number of comparison done by the C++ STl sort. I've been thinking about this for a while and my only solution is to write a class which has the member variable of type int and overload the operator < to count how many time it's called. I'd be grateful if anyone can suggest me a better way of doing it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
class INT
{
private:
	int i;
	static int count;
public:
	INT() {}
	~INT() {}
	INT (const int& a)
	{
		i = a;
	}

	INT& operator= (const int& i)
	{
		this->i = i;
		return *this;
	}

	bool operator < (const INT& a1)
	{
		count++;
		return this->i < a1.i;
	}

	int getCount ()const
	{
		return INT::count;
	}
};

int INT::count = 0;

int main()
{
	srand(time(0));
	vector<INT> v1;

	INT a[9] = {25, 6, 31, 27, 26, 40, 41, 30, 45};
	
	v1.push_back(a[0]);
	v1.push_back(a[1]);
	v1.push_back(a[2]);
	v1.push_back(a[3]);
	v1.push_back(a[4]);
	v1.push_back(a[5]);
	v1.push_back(a[6]);
	v1.push_back(a[7]);
	v1.push_back(a[8]);

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

	cout << a[1].getCount() << endl;

	return 0;
}


It will print 
21
Last edited on
Satan (369)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
int i{ 0 };

bool compare(int first, int second)
{
	i++;
	return (first < second);
}

int main(){

	vector<int> v1{ 0, 1, 2, 3, 4, 5, 6, 7, 8 };
	sort(v1.begin(), v1.end(), compare);

	for (auto i : v1) {
		cout << i << " ";
	}
	cout << "\nCompared: " << i << " times";
}
JLBorges (13770)
Write a custom comparison predicate for the sort and count how many times it is called.

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <numeric>

int main()
{
    std::mt19937 rng( std::random_device{}() ) ;

    for( std::size_t n = 10 ; n <= 1'000'000 ; n *= 10 )
    {
        std::vector<int> vec(n) ;
        std::iota( vec.begin(), vec.end(), 0 ) ;
        std::shuffle( vec.begin(), vec.end(), rng ) ;

        std::size_t n_comparisons = 0 ;
        const auto cmp = [&n_comparisons] ( int a, int b ) { ++n_comparisons ; return a<b ; };
        std::sort( vec.begin(), vec.end(), cmp ) ;
        std::cout << "N == " << vec.size() << "  #comparisons == " << n_comparisons << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/21fd979b710c6349

Same as Nwb's post above. Didn't see it when I made this post.
Last edited on
Song Tung (18)
Thanks for helping me
Topic archived. No new replies allowed.