Блог пользователя StellarSpecter

BogoSort (the best sorting algo)
Автор StellarSpecter, история, 3 месяца назад, По-английски

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 ?

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

!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).

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится 
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);
    }
}
→ Ответить