back to basics

[thedeemon]

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

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

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

Comments

[thedeemon.livejournal.com]

Sorting network делает 19 сравнений. Собсно, я от нее и плясал, дойдя до 14.

Поиск k-й порядковой статистики есть двусторонний сразу? А то если искать сначала в одну сторону, потом в другую, это слишком долго.

[diam-2003.livejournal.com]

Поиск порядковой статистики обычно делается на основе частичной сортировки.
Берём какую-нибудь достаточно хорошую сортирующую сеть и отрезаем лишнее.
Дальше получается задача комбинаторной оптимизации, чем-то похожая на построение оптимального умножителя на набор констант (c1, ..., cN) с использованием сложений-вычитаний и двоичного сдвига.

P.S. Не исключено, что можно проще. Это первое, что пришло в голову.