back to basics

[thedeemon]

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

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

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

Comments

[kgeorgiy.livejournal.com]

Посмотрим на элементы, с которым сравнивался найденный минимальный элемент. Каждый из них минимален в своем поддереве. Поэтому для любого другого элемента мы можем указать два небольших его элемента: минимум и вершина соответствующего поддерева. Следовательно искать второй минимум имеет смысл только среди тех элементов, с которыми мы сравнивали уже найденный минимум.

[thedeemon.livejournal.com]

Точно, спасибо!