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

[gmz]

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

---

Cross-posted from ZLog

Comments

[spamsink]

Какую к херам программульку?

(8*6+112*7)/120 = 6.9(3)

[gmz.livejournal.com]

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

[spamsink]

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

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

[gmz.livejournal.com]

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

[spamsink]

Я сказал не Шеннон, а Хаффман.

[kcmamu.livejournal.com]

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

[spamsink]

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

[kcmamu.livejournal.com]

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

[spamsink]

36 > 32

[kcmamu.livejournal.com]

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

А если "в худшем", то, например, подойдут 3 по 3 за 8 сравнений.

[spamsink]

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

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

[kcmamu.livejournal.com]

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.

[spamsink]

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

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

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

[kcmamu.livejournal.com]

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

[spamsink]

Тады ой.

[gmz.livejournal.com]

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

[gmz.livejournal.com]

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

[spamsink]

В отличие от где?

[gmz.livejournal.com]

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

[spamsink]

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

[gmz.livejournal.com]

Ага, направление мысли понятно.