back to basics

[thedeemon]

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

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

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

Comments

[sassa-nf.livejournal.com]

Если у вас цикл, то 14 сравнений никак не получится. А если не цикл, то много копипасты.

Это коммент о корректности вопроса. Можно было бы понять какую-то формулировку типа "нельзя быстрее, чем (n-1)*(n/4)", но тогда в последнее тоже много чего подходит; например, поиск максимума и минимума одновременно - (n-2); тогда поиск максимума и минимума в оставшемся - ещё (n-4); хотя самих сравнений может быть в 2 раза больше.

[thedeemon.livejournal.com]

Не цикл, копипаста ок.

[sassa-nf.livejournal.com]

14 - это максимум? у меня среднее выходит 13. Хотя, нужно пересчитать; из-за ленивости может быть меньше.

[thedeemon.livejournal.com]

Нет, у меня 14 всегда. А как с 13?

[sassa-nf.livejournal.com]

sort8 (s,t,u,v,w,x,y,z) = (if k < o then min l o else min k p, -- 2 comparisons
                           if n > r then max m r else max n q) where -- 2 comparisons
  ((a,b),(c,d)) = sort4 (s,t,u,v) -- 2 comparisons
  ((e,f),(g,h)) = sort4 (w,x,y,z) -- 2 comparisons
  ((k,l),(m,n)) = if a < c then -- 1 cmp
                    sort3 (a,b) (c,d) -- 1 or 2 cmps
                  else
                    sort3 (c,d) (a,b) -- 1 or 2 cmps
  ((o,p),(q,r)) = if e < g then -- 1 cmp
                    sort3 (e,f) (g,h) -- 1 or 2 cmps
                  else
                    sort3 (g,h) (e,f) -- 1 or 2 cmps

  sort3 (a,b) (c,d) = if b < c then ((a,b),(c,d))
                      else ((a,c), sort2 (b,d)) -- sorts the last 3 numbers
                      -- assuming a < b, a < c, c < d; 1 or 2 cmps
  sort2 (a,b) = if a < b then (a,b) else (b,a)
  sort4 (a,b,c,d) = (sort2 (a,b), sort2 (c,d))

видимо, есть ветвление, где может быть 2, а может быть 3 сравнения. Тогда есть 4 исхода: 4, 5, 5 и 6 сравнений в совокупности, а в среднем 5. Добавляем к остальным и получаем от 12 до 14, в среднем 13.

[thedeemon.livejournal.com]

Спасибо, попробую в свой интерпретатор засунуть для проверки...

[sassa-nf.livejournal.com]

проверка такая: [k,l,m,n] == sort [s,t,u,v]

[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]

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