StellarSpecter's blog

BogoSort (the best sorting algo)
By StellarSpecter, history, 3 months ago, In English

We generate permutation of given array randomly until we get it sorted.

It's expected complexity should be factorial n for n sized array, but I saw on google it's factorial n+1.

Can anyone explain to me how is it factorial n+1, because for a binomial distribution E(x) = 1/p(x).

Please purify my understanding.

Also is there any sorting algorithm better than bogosort ?

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +22 Vote: I do not like it

!n is the expected number of shuffles required to get to the sorted array, but after each shuffle you also need to check if it's sorted or not and that is why there should be an extra factor of n in the overall time complexity making it !(n+1).

→ Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it 
template <typename T>
void jokersort(std::vector<T> &v) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    auto v_copy = v;
    while (v != v_copy || !std::is_sorted(v.begin(), v.end())) {
        auto bogosort = [&gen](std::vector<T> &v) {
            while (!std::is_sorted(v.begin(), v.end())) {
                std::shuffle(v.begin(), v.end(), gen);
            }
        };
        bogosort(v);
        auto bozosort = [&gen](std::vector<T> &v) {
            std::uniform_int_distribution<> dis(0, v.size());
            while (!std::is_sorted(v.begin(), v.end())) {
                int i = dis(gen);
                int j = dis(gen);
                std::swap(v[i], v[j]);
            }
        };
        bozosort(v_copy);
    }
}
→ Reply