Рекурсия: различия между версиями

Известный алгоритм [[w:Быстрая сортировка|быстрой сортировки Хоара]] также основан на рекурсии. Пусть нам нужно отсортировать кусочек массива <math>A</math> от элемента с индексом <math>b</math> по элемент с индексом <math>e</math> включительно. Перераспределим элементы на этом кусочке так, чтобы вначале стояли элементы меньшие либо равные <math>A_b</math>, а потом элементы большие либо равные <math>A_b</math>. Пусть последний элемент в первом кусочке оказался на месте <math>c</math>. Вызовем рекурсивно сортировку двух кусочков от <math>b</math> до <math>c</math> и от <math>c + 1</math> до <math>e</math> включительно, (если, конечно, эти кусочки состоят более, чем из одного элемента). Воплотите эту идею в работающую процедуру сортировки массива. Проведите эксперименты по оценке средней глубины дерева рекурсии и времени работы алгоритма в зависимости от размера массива. Рассмотрите случаи а) случайного массива, б) массива, упорядоченогоупорядоченного по возрастанию, и в) массива, упорядоченного по убыванию.