naive birthday collision calculations: a raw quadratic loop seems faster than sorting

birthdays.cpp

#include <iostream>
#include <vector>
#include <random>

int main() {
    const int experiment_cnt = 1000;

    std::random_device rd;
    std::mt19937 generator(rd());
    std::uniform_int_distribution<int> distribution(1, 365);

    for(int n = 5; n <= 100; n += 5) {
        int collision_cnt = 0;
        std::vector<int> birthdays(n);

        for(int experiment = 1; experiment <= experiment_cnt; experiment++) {
            for(int person = 0; person < n; person++) {
                birthdays[person] = distribution(generator);
            }

            /*std::sort(birthdays.begin(), birthdays.end());
            
            for(int person = 1; person < n; person++) {
                if (birthdays[person] == birthdays[person-1]) {
                    collision_cnt++;
                    break;
                }
            }
            */
        
            bool found_collision = false;
            for(int person = 0; person < n-1; person++) {
                for(int other_person = person+1; other_person < n; other_person++) {
                    if (birthdays[person] == birthdays[other_person]) {
                        collision_cnt++;
                        found_collision = true;
                        break;
                    }
                }
                if (found_collision) { break; }
            }
        }

        double collision_fraction = static_cast<double>(collision_cnt) / 
            static_cast<double>(experiment_cnt);

        std::cout << "n = " << n << ": collision fraction = " << collision_fraction << '\n';
    }
}