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