?

Log in

Previous Entry | Next Entry

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

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


Cross-posted from ZLog

Comments

( 21 comments — Leave a comment )
spamsink
Jul. 17th, 2008 09:22 pm (UTC)
Какую к херам программульку?

(8*6+112*7)/120 = 6.9(3)
gmz
Jul. 17th, 2008 09:31 pm (UTC)
:) Я простой американский кодогенератор. И в целях поддержания профессионального тонуса то и дело чего-нибудь программирую. Моим работодателям не нужны ответы, им нужны программы.
spamsink
Jul. 17th, 2008 09:33 pm (UTC)
доказать, что пресловутый алгоритм даёт наилучшее среднее число сравнений

Хаффман в помощь.
gmz
Jul. 17th, 2008 09:48 pm (UTC)
Теория утверждает, что минимальное среднее не может быть меньше 6.90..., так что зазор для задачи некоторый есть.
spamsink
Jul. 17th, 2008 10:05 pm (UTC)
Я сказал не Шеннон, а Хаффман.
kcmamu
Jul. 17th, 2008 10:26 pm (UTC)
Тут возникает забавное направление: если N чисел сортируются в среднем за A сравнений, то одновременно две независимые кучки из N чисел в принципе можно сортировать быстрее, чем за 2A (если разрешается сравнивать не только сами числа, но и функции от них). В пределе (при N=const и "2→∞") до Шеннона дотягивается...
spamsink
Jul. 17th, 2008 10:34 pm (UTC)
Теоретически конечно, а вот нашел ли кто-нибудь уже такие N и k,
что k кучек из N чисел можно сортировать быстрее, чем за kA сравнений?
kcmamu
Jul. 17th, 2008 10:39 pm (UTC)
Не удивлюсь, если получится уже с двумя кучками по три числа.
spamsink
Jul. 17th, 2008 10:42 pm (UTC)
36 > 32
kcmamu
Jul. 17th, 2008 10:48 pm (UTC)
Во-первых, речь шла про "в среднем":
Хафман(6) = 8/3
Хафман(36) = 47/9 < 2*(8/3)

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

spamsink
Jul. 17th, 2008 11:02 pm (UTC)
Это понятно. Я спросил о худшем.
3 по 3 за 8 - подойдут, но как?

И чтобы в среднем стало быстрее, должна быть хоть одна комбинация перестановок, в котором сортировка "вместе" строго быстрее, чем сортировка этих перестановок по отдельности, что тоже неочевидно, как.
kcmamu
Jul. 17th, 2008 11:42 pm (UTC)
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
Jul. 17th, 2008 11:46 pm (UTC)
4) (a-c)(d-f)(g-i) ? 0

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

(a < c) ^ (d < f) ^ (g < i)
kcmamu
Jul. 17th, 2008 11:51 pm (UTC)
Preduprezhdal zhe: "если разрешается сравнивать не только сами числа, но и функции от них".
spamsink
Jul. 17th, 2008 11:57 pm (UTC)
Тады ой.
gmz
Jul. 17th, 2008 10:48 pm (UTC)
:( Недостаток образования сказывается. Кто ж знал, что мне выгоднее было бы в 76м на ВМК поступать, а не на мехмат.
gmz
Jul. 17th, 2008 11:54 pm (UTC)
А пальцем ткнуть можно в более или менее внятное изложение данного вопроса?
spamsink
Jul. 18th, 2008 12:02 am (UTC)
gmz
Jul. 18th, 2008 12:09 am (UTC)
Я это видел. У меня недостаточно образования, чтобы из кодирования на лету понять что-то про сортировку. Я имел в виду именно минимальное среднее число сравнений при сортировке. В теории и на практике для разных алгоритмов.
spamsink
Jul. 18th, 2008 12:14 am (UTC)
В данном случае перестановка кодируется результатами сравнений.

gmz
Jul. 18th, 2008 12:25 am (UTC)
Ага, направление мысли понятно.
( 21 comments — Leave a comment )

Profile

портрет, фрукты, селфи
gmz
Grzegorz Gogolewski

Latest Month

July 2017
S M T W T F S
      1
2345678
9101112131415
16171819202122
23242526272829
3031     

Tags

Powered by LiveJournal.com
Designed by Tiffany Chow