Развитием темы предыдущего пункта может служить следующая задача, тесно связанная также с упорядочением массивов.

адача 36. Составить рекурсивную программу-функцию нахождения k-го (k=1,2,…,n) наименьшего элемента одномерного массива, заданного вектором v = (v₀, v₁, ... , v_n-1).

Решение. Прежде всего уточним, что под k-м наименьшим элементом v понимается такой элемент bÎv, что a_i<b не более чем для k-1 значения индекса i и a_i£b не менее чем для k значений i. Например, 9 - третий и четвертый элементы последовательности 9, 8, 12, 1, 9, 11.

Одно из очевидных решений предложенной задачи состоит в следующем: упорядочиваем v по неубыванию и берем k-й по счету элемент полученной последовательности (счет от 1 и далее). Это можно сделать за c×n×log₂n операций, где c - константа. Однако имеются и более эффективные алгоритмы решения данной задачи. Например, в [12, с.117-122] приведены алгоритмы её решения за линейное и в среднем за линейное время - O(n) операций. Последний из них мы и разберем. Пусть решение задачи задается функцией fix(k,v).

Рекурсивная база. Если длина v равна единице, то решением может служить только элемент v₀ : 
fix(k,v) = v₀.

Декомпозиция. Пусть a - случайный элемент v и v1, v3 - подмассивы из v, причем в v1 помещены все элементы v меньшие a, а в v3 - большие a. Обозначим длины массивов v1 и v3 соответственно через k1 и k3. Далее будем рассуждать так. Если k£k1, то k-й по счету минимальный элемент следует искать в v1, и делать это можно рекурсивным обращением fix(k,v1). Если k1<k£n-k3, то искомый элемент просто равен a. И наконец, при n-k3<k£n искомый элемент следует искать в v3 и делать это можно рекурсивным обращением fix(k-(n-k3),v3).

В приведенной ниже программе в точности реализован описанный выше алгоритм:

v := (7    9    12    4    1    0    4    7    99)^T;

fix(1,v) = 0,   fix(2,v) = 1,   fix(4,v) = 4,   fix(9,v) = 99.