Стр. 82 - Основы алгоритмов и структур данных

80 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Separate (x, u, v, s)
{
v = v+ 1;
master = xu;
while (u < v)
{
for (u=u+1; ; u++)
{
if (xu > master) break;
}
for (v=v-1; v=u+1; v--)
{
if (x v < master) break;
}
< xu и xv меняем местами>
}
if (u>v)
{
< xu и xv меняем местами>
u =u-1;
}
s=u;
}
В процедуре деления каждый ключ сравнивается с ГЭ ровно 1 раз; число
сравнений О(j-i).
Кроме сравнения самих ключей, происходит также сравнение индексов.
Внутренние циклы отчасти дублируют ту проверку индексов, которая
происходит во внешнем цикле. В обоих внутренних циклах можно убрать
условия, а после цикла 1 раз проверить: а не замыкали ли друг друга
внутренние циклы.
Относительный порядок двух рекурсивных вызовов в общем случае может
быть любым. Однако при неудачном делении произвольный порядок
рекурсивных вызовов может привести к краху программы по следующим
причинам.
Легче всего рассмотреть этот аспект, исходя из природы рекурсивных
функций. Фактически, когда выполняется один из двух рекурсивных вызовов
параметры другого в явном или неявном виде сохраняются в стеке.
Пусть ГЭ – м оказался 2-й по убыванию элемент текущего массива. Пусть
первым выполняется рекурсивный вызов для левого подмассива 1 0 r r ≈ ,