back to basics

[thedeemon]

А вот кто не поленился дочитать книжки про построение алгоритмов, вас там научили их строить? Вот есть такая простейшая задачка: дан массив из 8 чисел, нужно найти "почти самое маленькое" и "почти самое большое", т.е.

sort(xs); return (xs[1], xs[6]);

Надо это сделать за минимальное число действий. Под действиями подразумеваются сравнения, ну и копирования с перестановками, хотя сравнения важнее. На особенности современного железа и его наборов инструкций пока положим, интересует классический теоретический подход. Как положено подходить к решению? Массив можно менять на месте, можно использовать дополнительную память. Я знаю, как это сделать за 14 сравнений. Можно ли за меньшее число? Можно ли доказать, что за меньшее нельзя?

Comments

[thedeemon.livejournal.com]

Перевел, работает, действительно от 12 до 14 сравнений делает.
if stats: min=12 max=14 avg=13.3333
swap stats: min=0 max=12 avg=6
copy stats: min=0 max=2 avg=1.57143
all stats: min=12 max=28 avg=20.9048
score=842922 ok=true


До этого у меня было:
if stats: min=14 max=14 avg=14
swap stats: min=0 max=10 avg=5.33333
copy stats: min=0 max=2 avg=1.57143
all stats: min=14 max=26 avg=20.9048
score=842912 ok=true

[sassa-nf.livejournal.com]

Интересно, что if stats avg больше 13. Я думал, что ветки по 1 и 2 сравнений будут равновероятны. Это, что ли, случай с a==b влияет так? Тогда нужно исправить условие, чтобы уходило по ветке с 1 сравнением, если равны.

sort3 (a,b) (c,d) = if b <= c then ((a,b),(c,d))
                      else ((a,c), sort2 (b,d))

[thedeemon.livejournal.com]

Это все зависит от того, как среднее считать, по каким данным. В моем случае прогонялось на всех перестановках [1..8], там a==b не бывает.

[sassa-nf.livejournal.com]

странно. каким тогда образом получаются ветви не равновероятны?