Пусть одномерный массив задан вектором v = (v0 v1 ... vn-1). Сортировка его простым выбором основана на следующей последовательности действий. Отыскиваем наименьший индекс k из тех элементов массива, которые больше или равны другим элементам массива. Далее меняем местами элементы vk и vn-1. После этого конечный элемент vn-1 можно оставить в покое и вести речь о сортировке оставшихся элементов, применяя к ним ранее описанную последовательность действий. Ясно, что, продолжая этот процесс, мы упорядочим весь исходный массив.
адача
1.
Составить рекурсивную программу-функцию
сортировки простым выбором массива,
заданного вектором v = (v0
v1 ... vn-1).
Решение. Описанная ранее процедура сортировки простым обменом явно рекурсивна. Декомпозицию можно проводить по длине массива, а базой рекурсии считать вектор длины 1. Соответствующая программа может быть задана функцией sortsel(v):
(3)
Контрольный пример:
