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

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