Чем я хуже Гильберта?

Пресловутый алгоритм сортировки пяти элементов за семь сравнений иногда даёт результат после 6го сравнения. Я не поленился, написал программульку, и оказалось, что среднее число сравнений – 6.93 (точнее 832/5! или 104/15).
Вот более интересная задача: доказать, что пресловутый алгоритм даёт наилучшее среднее число сравнений. Ну, или найти более шустрый в среднем алгоритм.

Cross-posted from ZLog

21 thoughts on “Чем я хуже Гильберта?”

    1. gmz Post author

      🙂 Я простой американский кодогенератор. И в целях поддержания профессионального тонуса то и дело чего-нибудь программирую. Моим работодателям не нужны ответы, им нужны программы.

  2. spamsink Post author

    доказать, что пресловутый алгоритм даёт наилучшее среднее число сравнений

    Хаффман в помощь.

    1. gmz Post author

      Теория утверждает, что минимальное среднее не может быть меньше 6.90…, так что зазор для задачи некоторый есть.

        1. kcmamu Post author

          Тут возникает забавное направление: если N чисел сортируются в среднем за A сравнений, то одновременно две независимые кучки из N чисел в принципе можно сортировать быстрее, чем за 2A (если разрешается сравнивать не только сами числа, но и функции от них). В пределе (при N=const и “2→∞”) до Шеннона дотягивается…

          1. spamsink Post author

            Теоретически конечно, а вот нашел ли кто-нибудь уже такие N и k,
            что k кучек из N чисел можно сортировать быстрее, чем за kA сравнений?

          2. kcmamu Post author

            Не удивлюсь, если получится уже с двумя кучками по три числа.

          4. kcmamu Post author

            Во-первых, речь шла про “в среднем”:
            Хафман(6) = 8/3
            Хафман(36) = 47/9 < 2*(8/3) А если "в худшем", то, например, подойдут 3 по 3 за 8 сравнений.

          5. spamsink Post author

            Это понятно. Я спросил о худшем.
            3 по 3 за 8 – подойдут, но как?

            И чтобы в среднем стало быстрее, должна быть хоть одна комбинация перестановок, в котором сортировка “вместе” строго быстрее, чем сортировка этих перестановок по отдельности, что тоже неочевидно, как.

          6. kcmamu Post author

            abc def ghi

            1) a?b
            2) d?e
            3) g?h

            Pri kazhdom variante otvetov — 27 uporjadochenij.
            Pustj, dlja opredeljonnosti, vezde vypalo “<". 4) (a-c)(d-f)(g-i) ? 0 5) (b-c)(e-f)(h-i) ? 0 otvety razbivajut prostranstvo vozmozhnyx konfiguracij na 4 gruppy: 7+7+7+6 V tex, gde "7", najdjotsja vopros (libo a?c, libo b?c, libo (a-c)(b-c)?0), deljashchij na 3+4; "6" voprosom a?c razbita na 2+4. Itogo: potracheno 6 voprosov, ostalosj 2-3-4 varianta. "4" vsegda odnim voprosom delitsja na 2+2; "3" delitsja na 1+2. Poslednij vopros (esli nuzhen) delit "2" na 1+1.

          7. spamsink Post author

            4) (a-c)(d-f)(g-i) ? 0

            Это красиво, но честно ли? Ведь это фактически

            (a < c) ^ (d < f) ^ (g < i)

          8. kcmamu Post author

            Preduprezhdal zhe: “если разрешается сравнивать не только сами числа, но и функции от них”.

        2. gmz Post author

          🙁 Недостаток образования сказывается. Кто ж знал, что мне выгоднее было бы в 76м на ВМК поступать, а не на мехмат.

        3. gmz Post author

          А пальцем ткнуть можно в более или менее внятное изложение данного вопроса?

          2. gmz Post author

            Я это видел. У меня недостаточно образования, чтобы из кодирования на лету понять что-то про сортировку. Я имел в виду именно минимальное среднее число сравнений при сортировке. В теории и на практике для разных алгоритмов.

          3. spamsink Post author

            В данном случае перестановка кодируется результатами сравнений.

Comments are closed.